#include cstdio
 
const int maxn = 50001;
const int inf = 1  30;
 
FILE in = fopen(dijkstra.in,r), out = fopen(dijkstra.out,w);
 
struct graf
{
    int nod, cost;
    graf next;
};
 
int n, m;
graf a[maxn];
int d[maxn], h[maxn], poz[maxn], k;
 
void add(int where, int what, int cost)
{
    graf q = new graf;
    q-nod = what;
    q-cost = cost;
    q-next = a[where];
    a[where] = q;
}
 
void read()
{
    fscanf(in, %d %d, &n, &m);
 
    int x, y, z;
    for ( int i = 1; i = m; ++i )
    {
        fscanf(in, %d %d %d, &x, &y, &z);
        add(x, y, z);
    }
}
 
void swap(int x, int y)
{
    int t = h[x];
    h[x] = h[y];
    h[y] = t;
}
 
void upheap(int what)
{
    int tata;
    while ( what  1 )
    {
        tata = what  1;
 
        if ( d[ h[tata] ]  d[ h[what] ] )
        {
            poz[ h[what] ] = tata;
            poz[ h[tata] ] = what;
 
            swap(tata, what);
 
            what = tata;
        }
        else
            what = 1;
    }
}
 
void downheap(int what)
{
    int f;
    while ( what = k )
    {
        f = what;
        if ( (what1) = k )
        {
            f = what  1;
            if ( f + 1 = k )
                if ( d[ h[f + 1] ]  d[ h[f] ] )
                    ++f;
        }
        else
            return;
 
        if ( d[ h[what] ]  d[ h[f] ] )
        {
            poz[ h[what] ] = f;
            poz[ h[f] ] = what;
 
            swap(what, f);
 
            what = f;
        }
        else
            return;
    }
}
 
void dijkstra_heap()
{
    for ( int i = 2; i = n; ++i )
        d[i] = inf, poz[i] = -1;
    poz[1] = 1;
 
    h[++k] = 1;
 
    while ( k )
    {
        int min = h[1];
        swap(1, k);
        poz[ h[1] ] = 1;
        --k;
 
        downheap(1);
 
        graf q = a[min];
 
        while ( q )
        {
            if ( d[q-nod]  d[min] + q-cost )
            {
                d[q-nod] = d[min] + q-cost;
 
                if ( poz[q-nod] != -1 )
                    upheap( poz[q-nod] );
                else
                {
                    h[++k] = q-nod;
                    poz[ h[k] ] = k;
                    upheap( k );
                }
            }
            q = q-next;
        }
    }
}
 
int main()
{
    read();
    dijkstra_heap();
 
    for ( int i = 2; i = n; ++i )
        fprintf(out, %d , d[i] == inf  0  d[i]);
    fprintf(out, n);
 
    return 0;
}