#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;
}