#include <iostream>
#include <fstream>
#include <queue>
#include <stdlib.h>
using namespace std;
#define inf 2000000000
struct drum
{
    int x,c;
    bool operator <(const drum& q) const{
        return c>q.c;
    }
};
priority_queue<drum> pq;
int d[50001],**c,**l,n,m,ok=1;
int main()
{
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    f>>n>>m;
    c=(int **)malloc((n+1)*sizeof(int*));
    l=(int **)malloc((n+1)*sizeof(int*));
    for(int i=1;i<=n;i++)
        {
            c[i]=(int*)malloc(sizeof(int));
            c[i][0]=0;
            l[i]=(int*)malloc(sizeof(int));
            l[i][0]=0;
            d[i]=inf;
        }
    int a,b,s;
    for(int i=1;i<=m;i++)
    {
        f>>a>>b>>s;
        c[a][0]++;
        c[a]=(int *)realloc(c[a],(c[a][0]+1)*sizeof(int));
        c[a][c[a][0]]=s;
        l[a][0]++;
        l[a]=(int *)realloc(l[a],(l[a][0]+1)*sizeof(int));
        l[a][l[a][0]]=b;
    }
    for(int i=1;i<=c[1][0];i++)
    {
        drum q;
        d[l[1][i]]=c[1][i];
        q.c=c[1][i];
        q.x=l[1][i];
        pq.push(q);
    }
    while(!pq.empty())
    {
        drum q=pq.top();
        pq.pop();
        ok=0;
        if(q.c<=d[q.x])
        {
        for(int i=1;i<=c[q.x][0];i++)
            if(d[l[q.x][i]]>d[q.x]+c[q.x][i])
            {
                d[l[q.x][i]]=d[q.x]+c[q.x][i];
                drum p;
                p.c=d[l[q.x][i]];
                p.x=l[q.x][i];
                pq.push(p);
            }
        }
    }
    for(int i=2;i<=n;i++)
        if(d[i]==inf)
            g<<"0 ";
        else
            g<<d[i]<<' ';
    return 0;
}