#include<fstream>
#include<vector>
#include<queue>

#define inf 2000000000

using namespace std;

int D,S,n,m,cost[700][700],nr,sol,sw[1000],best[1000],flux[700][700],tsol[1000],t[1000];



vector <int> v[700];

queue <int> q;

void afisare ()
{
	int i;
	ofstream g("cmcm.out");
	g<<nr<<' '<<sol<<"\n";
	for (i=n+1;i<S;i++)
		if (tsol[i])
			g<<tsol[i]<<' ';
	g.close();
}

int getflux()
{
	int val,i,p;
	vector<int> :: iterator it;
	
	q.push(S);
	memset(sw,0,sizeof(sw));
	sw[S]=1;
	
	for (i=1;i<=D;i++)
		best[i]=inf;
	best[S]=0;
	
	while (!q.empty())
	{
		val=q.front();
		q.pop();
		sw[val]=0;
		for (it=v[val].begin();it<v[val].end();++it)
			if (flux[val][*it]<=0 && best[*it]>best[val]+cost[val][*it])
			{
				best[*it]=best[val]+cost[val][*it];
				if (sw[*it]==0)
				{
					q.push(*it);
					sw[*it]=1;
				}
				t[*it]=val;
			}
	}
	
	if (best[D]<inf/2)
	{
		sol+=best[D];
		p=D;
		while (p!=S)
		{
			flux[t[p]][p]++;
			flux[p][t[p]]--;
			tsol[p]=t[p];
			p=t[p];
			
		}
		return 1;
	}
	
	return 0;
}

	

void execute ()
{
	int fl=1;
	while (fl)
	{
		fl=getflux();
		nr++;
	}
}

void citire ()
{
	int i,e,a,c,b;
	ifstream f ("cmcm.in");
	f>>n>>m>>e;
	for (i=1;i<=e;i++)
	{
		f>>a>>b>>c;
		cost[a][b]=c;
		cost[b][a]=-c;
		v[a].push_back(b+n);
		v[b+n].push_back(a);
	}
	
	S=n+m+1;
	D=S+1;
	
	for (i=1;i<=n;i++)
	{
		v[S].push_back(i);
		cost[S][i]=0;
	}
	
	for (i=n+1;i<S;i++)
	{
		v[i].push_back(D);
		cost[i][D]=0;
	}
	f.close();
}

int main()
{
	citire ();
	execute();
	afisare ();
	return 0;
}