#include <fstream>
#include <vector>
#include <set>

using namespace std;

#define NAGY 99999999

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

int n,i,a,b,c,x[1<<19][19],mini,j,k,m,hossz[19][19];
struct adat
{
    vector<int>ut;
};
vector<adat>csp;

int main()
{
    cin>>n>>m;
    for(i=1;i<=n;++i)
    for(j=1;j<=n;++j)
    hossz[i][j]=NAGY;
    csp.resize(n);
    for(i=1;i<=m;++i)
    {
        cin>>a>>b>>c;
        csp[a].ut.push_back(b);
        hossz[a][b]=c;
    }


    for(i=0;i< 1<<(n+1);++i)
    for(j=0;j<=n;++j)
    x[i][j]=NAGY;

    x[1][0]=0;

    for(i=0;i< (1<<n);++i)
    for(j=0;j<n;++j)
    if(i & (1<<j) )
    {
        for(auto k : csp[j].ut)
        if(i & (1<<k) )
        x[i][k]=min(x[i][k],x[i^ (1<<k)][j]+hossz[j][k]);
    }

    for(i=0;i< (1<<n);++i)
    {
        for(j=0;j<n;++j)
            cout<<x[i][j]<<" ";
        cout<<'\n';
    }


    mini=NAGY;

    for(i=0;i<n;++i)
    mini=min(mini,x[1<<n-1][i]+hossz[i][0]);

    if(mini!=NAGY) cout<<mini<<"\n";
    else cout<<"Nu exista solutie\n";

    return 0;
}