#include <fstream>
#include <vector>
#include <climits>
#include <deque>
#include <algorithm>
#include <string>

#define MOD 1999999973
#define EPSILON 0.001

using namespace std ;

ifstream cin ("hamilton.in") ;
ofstream cout ("hamilton.out") ;

int n, viz[100009], mnx ;

vector<pair<int, int> > m[100009] ;

long long fil(int nod, int noduri, int cost)
{
    if(noduri == n && nod == 0)
    {
        return cost ;
    }

    if(viz[nod])return INT_MAX ;

    viz[nod] = 1 ;

    if(cost >= mnx)return INT_MAX ;

    long long mn = INT_MAX ;

    for(int f = 0 ; f < m[nod].size() ; f ++)
        mn = min(mn, fil(m[nod][f].first, noduri + 1, cost + m[nod][f].second)), mnx = mn ;

    cout << mn << " " ;

    viz[nod] = 0 ;

    return mn ;
}

int kk[100009] ;

long long fil(int nod, int noduri, int cost, int k)
{
    if(noduri == n && nod == 0)
    {
        ///for(int f = 0 ; f < n ; f ++)
            ///cout << viz[f] << " ";

        ///cout << cost << endl ;

        return cost ;
    }

    if(viz[nod])return INT_MAX ;

    viz[nod] = k ;

    long long mn = INT_MAX ;

    for(int f = 0 ; f < m[nod].size() ; f ++)
        mn = min(mn, fil(m[nod][f].first, noduri + 1, cost + m[nod][f].second, k + 1)) ;

    viz[nod] = 0 ;

    return mn ;
}


int main()
{
    int q ;

    cin >> n >> q ;

    while(q --)
    {
        int a, b, c ;

        cin >> a >> b >> c ;

        m[a].push_back({b, c}) ;
    }

    long long a = fil(0, 0, 0, 1) ;

    if(a != INT_MAX)cout << a ;
        else cout << "Nu exista solutie" ;

    return 0 ;
}