#include <fstream>
#define inf 50000001
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout ("dijkstra.out");

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;
    fin>>a>>b>>di;
    d=new node;
    d->nr=b;
    d->dist=di;
    d->next=v[a];
    v[a]=d;
}

void dijkstra ()
{
    int i,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 (vis[p->nr]==0&&s<d[p->nr]) d[p->nr]=s;
            p=p->next;
        }
        vis[current]=1;
        mind=inf;
        for (i=2;i<=n;i++) if (!vis[i]) if(d[i]<mind) {mind=d[i]; current=i;}
    }
}

int main()
{
    int i;
    fin>>n>>m;
    for (i=1;i<=m;i++) build_graph ();
    dijkstra ();
    for (i=2;i<=n;i++) fout<<d[i]<<" ";
}