#include<fstream>
#include<vector>
#include<iostream>
#include<cstring>
#define N 19
#define dim 262150
#define Inf 342000001

using namespace std;

vector<int> GT[N];
int n,m,cost[N][N],dp[dim][N],ans;

void read()
{
    ifstream fin("hamilton.in");
    fin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        cost[i][j]=Inf;
    for(int i=1;i<=m;i++)
    {
        int x,y,c;
        fin>>x>>y>>c;
        GT[y].push_back(x);
        cost[x][y]=c;
    }
    fin.close();
}

int solve_dp(int start,int mask,int k)
{
    if(k==start && mask==(1<<start)) return dp[start][1<<start]=0;
    if(dp[mask][k]==-1)
    {
        dp[mask][k]=Inf;
        vector<int>::iterator it;
        for(it=GT[k].begin();it!=GT[k].end();it++)
        {
            if(mask & (1<<(*it)))
                {
                    if((*it)==start && (mask & ~(1<<k))!=(1<<start) ) continue;
                    dp[mask][k]=min(dp[mask][k],solve_dp(start,mask & ~(1<<(k)),*it)+cost[*it][k]);
                }
        }
    }

    return dp[mask][k];

}


void solve()
{
    ofstream fout("hamilton.out");
    int i,j,ans=Inf;
    for(i=0;i<n;i++)
    {
        memset(dp,-1,sizeof(dp));
        vector<int>::iterator it;
        for(it=GT[i].begin();it!=GT[i].end();it++)
           {
               ans=min(ans,solve_dp(i,(1<<n)-1,(*it))+cost[*it][i]);
               //cout<<(*it)<<' '<<ans<<' ';
           }
        cout<<i<<' '<<ans<<endl;
    }
    if(ans!=Inf) fout<<ans;
    else fout<<"Nu exista solutie";
    fout.close();

}


int main()
{
    read();
    solve();

}