rt.

#include <iostream>
#include <stdio.h>
#include <map>
#define mod 1000000000
#define int long long
using namespace std;
int n,m,k,center;
int u[300003],v[300003],type[300003],fa[300003],e[300003];
int findfa(int u)
{
	if(fa[u]!=u)
		fa[u] = findfa(fa[u]);
	return fa[u];
}
void hebin(int u,int v)
{
	int fu = findfa(u),fv = findfa(v);
	if(fu!=fv)
		fa[fu] = fv;
	return ;
}
inline int pow(int a,int b)
{
	int ans = 1;
	while(b)
	{
		if(b&1)
			ans = (ans*a)%mod;
		a = (a*a)%mod;
		b >>= 1;
	}
	return ans;
}
int calc(int w)
{
	bool s;
	for(int i=1;i<=n+m-1;i++)
		fa[i] = i,e[i] = 0;
	for(int i=1;i<=k;i++)
	{
		if(u[i]==1&&v[i]==1)
			continue;
		
		s = w^type[i];
		if(u[i]%2||v[i]%2)
		{
			if(s==0)
				hebin(u[i],v[i]);
			else
			{
				if(findfa(u[i])==findfa(v[i]))
					return 0;
				if(e[u[i]]==0)
					e[u[i]] = v[i];
				if(e[v[i]]==0)
					e[v[i]] = u[i];
				hebin(u[i],e[v[i]]);
				hebin(e[u[i]],v[i]);
			}
		}
		else
		{
			if(s==1)
				hebin(u[i],v[i]);
			else
			{
				if(findfa(u[i])==findfa(v[i]))
					return 0;
				if(e[u[i]]==0)
					e[u[i]] = v[i];
				if(e[v[i]]==0)
					e[v[i]] = u[i];
				hebin(u[i],e[v[i]]);
				hebin(e[u[i]],v[i]);
			}
		}
		
		
	}
	int ans = 0;
	for(int i=1;i<=n+m-1;i++)
		if(findfa(i)==i)
			printf("%d ",i),
			ans++;
	printf("\n%d\n",ans-1);
	return pow(2,ans-1);
}
signed main()
{
	scanf("%lld%lld%lld",&n,&m,&k);
	center = -1;
	for(int i=1;i<=k;i++)
	{
		scanf("%d%d%d",&u[i],&v[i],&type[i]);
		if(u[i]==1&&v[i]==1)
			center = type[i];
		if(v[i]>1)
			v[i] = n+v[i]-1;
	}
	if(center!=-1)
		printf("%lld",calc(center));
	else
		printf("%lld",(calc(0)+calc(1))%mod);
	return 0;
}