#include <stdio.h>
#include <string.h>

#define Inf 0x3f3f3f3f
#define Nmax 50001

int x[5*Nmax],y[5*Nmax],c[5*Nmax];
int d[Nmax];
int n,m;

int main()
{
    int i,j,ok;
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    
    scanf("%d %d\n", &n,&m);
    
    memset(d,0,sizeof(d));
    
    for (i=1;i<=m;++i)
    {
        scanf("%d %d %d\n", &x[i], &y[i], &c[i]);
        if (x[i]==1)
            d[y[i]]=c[i];
    }
    
    for (i=2;i<=n;++i)
          if (d[i]==0)
              d[i]=Inf; 
    
    ok=0;
    while(!ok)
    {
        ok=1;  
        for (i=1;i<=m;++i)
              if (d[y[i]]>d[x[i]]+c[i])
                  d[y[i]]=d[x[i]]+c[i],
                  ok=0;
    }
    
    for (i=2;i<=n;++i)
          if (d!=Inf) printf("%d ", d[i]);
               else printf("%d ", !ok);
    return 0;
}