#include<bits/stdc++.h>
#define pii pair<int,int>
#define x first
#define y second
#define N 50

using namespace std;

int n,m,b[N];
int mn=1e9;
int d[N];
int rs=1e9,viz[N];
vector<pii>V[N];

void DFS(int x, int h, int c) {
    viz[x]=1;
    d[h]=x;
    for (auto it:V[x]) {
        if (h==n && it.x==d[1]) {
            rs=min(rs,c+it.y);
            break;
        } else if (!viz[it.x]) {
            DFS(it.x,h+1,it.y+c);
        }
    }
    viz[x]=0;
    d[h]=0;
}

int main() {
    ifstream cin("hamilton.in");
    ofstream cout("hamilton.out");
    cin>>n>>m;
    for (int i=1; i<=m; ++i) {
        int x,y,c; cin>>x>>y>>c;++x; ++y;
        V[x].push_back({y,c});
    }
    DFS(1,1,0);
    if (rs<1e9) cout<<rs;
    else cout<<"Nu exista solutie";

    return 0;
}