#include <iostream>
#include <vector>
#include <set>
#include <stdio.h>
#define MAXN 50100
#define INF 1000000000

using namespace std;

FILE *f=fopen("dijkstra.in","r");
FILE *g=fopen("dijkstra.out","w");

vector <int> p[MAXN],c[MAXN];
set< pair <int,int> >t;

int n,d[MAXN],m,i;
void dijkstra()
{
    int i,val,x;
    for(i=1;i<=n;i++)d[i]=INF;
    t.insert(make_pair(0,1));
    while(t.size()>0)
    {
        val = (*t.begin()).first;
        x = (*t.begin()).second;
        t.erase(*t.begin());
        for(i=0;i<p[x].size();i++)
        if(d[p[x][i]]>val+c[x][i])
        {
            d[p[x][i]]=val+c[x][i];
            t.insert(make_pair(d[p[x][i]],p[x][i]));
        }
    }

}
void citire()
{
    int a,b,d;
    fscanf(f,"%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        fscanf(f,"%d%d%d",&a,&b,&d);
        p[a].push_back(b);
        c[a].push_back(d);
    }
}

int main()
{
    citire();
    dijkstra();
    for(i = 2; i <= n; i++)
        fprintf(g,"%d ", d[i] == INF ? 0 : d[i]);
    return 0;
}