# include <stdlib.h>
# include <cstdio>
# include <iterator>

using namespace std;

int h[200005],n,poz[200005],a[200005];

struct camp
{
       int info,cost;
       camp *next;
}*G[10000];


int tata(int nod)
{
    return nod / 2;
}
int fiust(int nod)
{
    return nod * 2;
}
int fiudr(int nod)
{
    return nod * 2 + 1;
}
int min()
{
    return h[1];
}

void add(const int &x,const int &y,const int &c)
{
     camp *p;
     p = new camp;
     p -> info = y;
     p -> cost = c;
     p -> next = G[x];
     G[x] = p;
}     
void swap(int &x, int &y)
{int aux;
     aux = x; 
     x = y;
     y = aux;
     }
void sift( int k)
{int son;
     do
     {
         son = 0;
         if (fiust(k) <= n)
         {
            son = fiust(k);
            if (fiudr(k) <= n && a[h[fiust(k)]] > a[h[fiudr(k)]])
            son = fiudr(k);
            }
         if (a[h[son]] >= a[h[k]]) son = 0;
     
     if (son)
     {
             poz[h[son]] = k;
             poz[h[k]] = son;
             swap(h[k],h[son]);
             k = son;
             
             }
     }while (son);
}
            
void perc( int k)
{int key;
     key = h[k];
     while (k > 1 && a[key] < a[h[tata(k)]])
     {
           h[k] = h[tata(k)];
           poz[h[tata(k)]] = k;
           k = tata(k);
           }
     h[k] = key;
     poz[key] = k; 
     
     }

int pop()
{int r;
     r = h[1];
     h[1] = h[n];
     poz[h[n]] = 1;
     --n;
     
     sift(1);
     return r;     
     }
void push(int k)
{
     h[++n] = k;
     poz[k] = n;
     perc(n);
     }


int main()
{int ct;
     camp *it;
    int x,y,i,m,c,d[10000];
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    
    ct = 0;
    scanf("%d%d",&n,&m);
    for (i = 1; i <= m; i++)
    {
        scanf("%d%d%d",&x,&y,&c);
        add(x,y,c);
        }
    
    while(n)
    {
            x = pop();
            for (it = G[x]; it; it = it -> next)
            {
                y = it->info;
                c = it->cost;
                
                if (!poz[y])
                {
                            d[y] = d[x] + c;
                            push(y);
                            }
                if (d[y] > d[x] + c)
                d[y] = d[x] + c;
                sift(poz[y]);
                }
            }
                for (i = 2; i <= n; i++)
                printf("%d",d[i]);

                
return 0;
}