#include<fstream>
#include<vector>
#include<iostream>

using namespace std;

int cost[20][20];
vector<int> a[20];
int viz[20];
int j,n,m,mx,x,y,z;

void hamilton(int x, int nr, int sum)
{
	int i;
	viz[x]=1;
	for (i=0;i<a[x].size();++i)
	{
		z=a[x][i];
		if (viz[z]==0)
		{		
			cout<<x<<" "<<a[x][i]<<" "<<viz[z]<<"\n";	
			hamilton(a[x][i], nr+1, sum+cost[x][a[x][i]]);
		}
		if (nr==n && cost[x][0]!=0 && sum+cost[x][0]<mx) mx=sum+cost[x][0];
	}
	viz[x]=0;
}

int main(){
	ifstream f("hamilton.in");
	ofstream g("hamilton.out");
	
	f>>n>>m;
	
	for (j=0;j<m;++j)
	{
		f>>x>>y>>z;
		a[x].push_back(y);
		cost[x][y]=z;
	}
	
	for (x=0;x<n;++x)
	{
		cout<<"lista"<<x<<"\n";
		for(y=0;y<a[x].size();++y)
			cout<<a[x][y]<<" ";
		cout<<"\n";
	}

	mx=2000000000;
	
	cout<<"intram in functia recursiva!!!\n";
	
	hamilton(0,1,0);
	
	if (mx==2000000000) g<<"Nu exista solutie\n";
	else g<<mx<<"\n";
	
	f.close();
	g.close();
}