#include <iostream>

using namespace std;

/*

5 8

1 2 2

1 5 10

2 3 3

2 5 7

3 1 4

3 4 4

4 5 5

5 3 3

min: 9

--------------------------------

Process exited with return value 0

Press any key to continue . . .

*/

const int infinity = 999999;

int minnum = infinity;

int vertx, edge;

int Graph[20][20] = {0}, book[20] = {0};

void DFS(int _n, int _dis)

{

	if(_dis > minnum) return;

	if(_n == vertx)

	{

		if(_dis < minnum)

		{

			minnum = _dis;

		}

		return;

	}

	for(int i = 1; i <= vertx; i++)

	{

		if(Graph[_n][i] != infinity && book[i] == 0)

		{

			book[i] = 1;

			DFS(i, _dis + Graph[_n][i]);

			book[i] = 0;

		}

	}

}

int main()

{

	cin >> vertx >> edge;

	for(int i = 1; i <= vertx; i++)

	{

		for(int j = 1; j <= vertx; j++)

		{

			if(i == j)

			{

				Graph[i][j] = 0;

			}

			Graph[i][j] = infinity;

		}

	}

	for(int i = 1; i <= edge; i++)

	{

		int x, y, z;

		cin >> x >> y >> z;

		Graph[x][y] = z;

	}

	DFS(1, 0);

	cout << endl << "min: " << minnum;

	return 0;

}