#include <iostream>
#include <fstream>
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
ofstream fout("cv.txt");
int n,m,k;
int a[20][20];
int b[20][20];
int st[10001];
int v[20];
char X[20];
bool sol()
{
    int i,j;
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
        if(b[i][j]>0) return false;
    return true;
}
void LATIME(int x)
{
    int i,j;
    st[++k]=x;
    while(k>0)
    {
        i=st[k--];
        for(j=0;j<n;j++)
        if(b[i][j]) {st[++k]=j; b[i][j]=0;}
    }
}
bool valid(int k)
{
    int i;
    for(i=1;i<k;i++)
    if(v[i]==v[k]) return false;
    return true;
}
void afisare(int k)
{
    int i;
    for(i=1;i<=k;i++)
    fout<<v[i];
    fout<<'\n';
}
void bkt(int k)
{
    int i;
    for(i=1;i<=n;i++)
    {
        v[k]=i;
        if(valid(k))
        {
            if(k==n) afisare(k);
            else bkt(k+1);
        }
    }
}
int main()
{
    f>>n>>m;
    int i,j,d,c;
    for(d=1;d<=m;d++)
    {
        f>>i>>j>>c;
        a[i][j]=b[i][j]=c;
    }
    f.close();
    ifstream f("hamilton.in");
    f>>i>>j;
    f>>i;
    LATIME(i);
    if(!sol()) g<<"Nu exista solutie";
    else
    {
        bkt(1);
        fout.close();
        ifstream fin("cv.txt");
        m=10000001;
        int A,B;
        while(fin>>X)
        {
            int s=0;
            X[n]=X[0];
            for(i=0;i<n;i++)
            {
                A=X[i]-49;
                B=X[i+1]-49;
                if(a[A][B]==0) i=n+13;
                else s+=a[A][B];
            }
            if(s<m and i<n+13) m=s;
        }
        g<<m;
    }
    return 0;
}