#include <iostream>
#include <fstream>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
const int maxn=50001;
const int inf=1<<30;

struct graf
{
    int nod, cost;
    graf *next;
};

int n, m;
graf *a[maxn];
int d[maxn], q[maxn];
void add(int x, int y, int cost)
{
    graf *q = new graf;
    q->nod = y;
    q->cost = cost;
    q->next = a[x];
    a[x] = q;
}
void dijkstra()
{
    for(int i=2; i<=n; i++)
        d[i]=inf;
    for(int i=1; i<=n; i++)
    {
        int mini=inf,pmin;
        for(int j=1; j<=n; j++)
            if(q[j]==0 && d[j]<mini)
        {
            mini=d[j]; pmin=j;
        }
        q[pmin]=1;
        graf *t=a[pmin];
        while(t)
        {if(d[t->nod]>t->cost+d[pmin]) d[t->nod]=t->cost+d[pmin];
        t=t->next;}
    }
}
int main()
{
    f>>n>>m;
    int x,y,z;
    for(int i=1; i<=m; i++)
    {
        f>>x>>y>>z;
       add(x,y,z);
    }
    dijkstra();
    for(int i=2; i<=n; i++)
        g<<d[i]<<' ';
    g<<'\n';
}