#include<stdio.h>
#include<queue>
#define MAXN 1<<16
#define MARE 0x3f3f3f3f

using namespace std;

struct nod{int x,d;nod *urm;};

nod *q,*g[MAXN];
int i,j,n,x,y,d,m;
int inq[MAXN],dmin[MAXN];

void add(int y,int x,int d)
{
    nod *p;
    p=new nod;
    p->x=x;
    p->d=d;
    p->urm=g[y];
    g[y]=p;
}

int main(void)
{
    queue <int> Q;
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d%d",&n,&m);

    for(i=1;i<=n;i++)
    {
        dmin[i]=MARE;
        g[i]=0;
    }

    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&d);
        add(x,y,d);
    }
    dmin[1]=0;
    Q.push(1);
    inq[1]=0;
    while(!Q.empty())
    {
        x=Q.front();
        Q.pop();
        inq[x]=0;
        for(q=g[x];q!=0;q=q->urm)
        {
            if(dmin[x] + (q->d) < dmin[q->x])
            {
                dmin[q->x]=dmin[x] + q->d;
                if(!inq[q->x])
                {
                    Q.push(q->x);
                    inq[q->x]=1;
                }
            }
        }
    }
    j=0;
    for(i=2;i<=n;i++)
    {
       printf("%d",dmin[i] < MARE ? dmin[i] : j);
    }
    return 0;
}