#include <cstdio>
#define inf 50000001
using namespace std;
FILE *in = fopen("dijkstra.in","r"), *out = fopen("dijkstra.out","w");
struct node
{
    int nr,dist;
    node *next;
} *v[50001];

int d[50001],n,m; bool vis[50001];

void build_graph ()
{
    int a,b,di;
    node *d;
    fscanf(in, "%d %d %d", &a, &b, &di);
    d=new node;
    d->nr=b;
    d->dist=di;
    d->next=v[a];
    v[a]=d;
}

void dijkstra ()
{
    int i,j,current,mind=0,s; node *p;
    for (i=1;i<=n;i++) d[i]=inf;
    d[1]=0; current=1;
    while (mind!=inf)
    {
        p=v[current];
        while (p!=NULL)
        {
            s=d[current]+p->dist;
            if (s<d[p->nr]) d[p->nr]=s;
            p=p->next;
        }
        vis[current]=1;
        mind=inf;
        for (j=2;j<=n;j++) if (!vis[j]&&d[j]<mind) {mind=d[j]; current=j;}
    }
}

int main()
{
    int i;
    fscanf(in, "%d %d", &n, &m);
    for (i=1;i<=m;i++) build_graph ();
    dijkstra ();
    for (i=2;i<=n;i++) if (d[i]==inf) d[i]=0;
    for (i=2;i<=n;i++) fprintf(out, "%d ", d[i]);
}