#include <fstream>
#include <cstring>
using namespace std;

ofstream g("dijkstra.out");

unsigned int INF=2000000000;

int N, M, x, y, z, D[50001], prim, ultim;
struct nod{int info; nod *urm; int dist;} *li[50001], *p;
bool viz[50001];

void push(nod *&li, int info, int dist)
{
    p=new nod();
    p->info=info;
    p->dist=dist;
    p->urm=li;
    li=p;
}

int minim(int D[], int &A)
{
    y=INF;
    for(x=1;x<=N;x++)
        if(D[x]<y && !viz[x])
            y=D[x], A=x;
    return y;
}

void dij()
{
    for(z=2;z<=N;z++)   D[z]=INF;
    int A;
    int m=minim(D, A);
    while(m != INF)
    {
        viz[A]=true;
        for(nod *B=li[A];B;B=B->urm)
            if(D[A] + B->dist < D[B->info])
                D[B->info]=D[A]+B->dist;
        m=minim(D, A);
    }

}

int main()
{
    int i;

    FILE *f;f=fopen("dijkstra.in", "r");
    fscanf(f, "%d%d", &N, &M);

    for(i=1;i<=M;i++)
    {
        fscanf(f, "%d%d%d", &x, &y, &z);
        push(li[x], y, z);
    }

    dij();

    for(i=2;i<=N;i++)
        g<<D[i]<<" ";
    return 0;
}