#include <iostream>
#include <fstream>
#define maxN 50005
#define maxM 250005
#define INF 0x3f3f
using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int n,m,d[maxN],saw[maxN];

struct graf
{
    int nod,cost;
    graf *next;
} *G[maxN];

void addN(int x,int y,int z)
{
    graf *q;
    q=new graf;
    q->nod=y;
    q->cost=z;
    q->next=G[x];
    G[x]=q;
}

void read()
{
    int i,a,b,c;
    f>>n; f>>m;
    for(i=1; i<=m ;i++)
    {
        f>>a; f>>b; f>>c;
        addN(a,b,c);
    }
    for(i=1; i<=n ;i++)
    {
        saw[i]=0;
        d[i]=INF;
    }
    d[1]=0;
}

void dijkstra()
{
    graf *q;
    int min,nod=-1,i,j;
    for(i=1; i<=n ;i++)
    {
        min=INF;
        for(j=1; j<=n ;j++)
        {
            if(!saw[j] && min>d[j])
            {
                min=d[j];
                nod=j;
            }
        }

        saw[nod]=1;
        for(q=G[nod]; q!=NULL ;q=q->next)
        {
            if(d[q->nod]>d[nod]+q->cost)
            {
                d[q->nod]=d[nod]+q->cost;
            }
        }
    }
}

void print()
{
    for(int i=2; i<=n ;i++)
        g<<d[i]<<" ";
}

int main()
{
    read();
    dijkstra();
    print();
    return 0;
}