#include<set>
#include<vector>
#include<fstream>
#include<cstdio>
#define mp make_pair
#define pb push_back
#define MAX_N 50005
#define INFI 2147483647
using namespace std;

int n, m, d[MAX_N], t[MAX_N];
vector<int> G[MAX_N], C[MAX_N];
set< pair<int, int> > Q;

void citire()
{
    int a, b, c, i;
    ifstream fin("dijkstra.in");
    fin>>n>>m;
    for(i=1; i<=m; i++)
    {
        fin>>a>>b>>c;
        G[a].pb(b);
        C[a].pb(c);
    }
}

void dijkstra()
{
    int i, val, x;
    for(i=2; i<=n; i++)
        d[i]=INFI, t[i]=-1;
    t[1]=0, d[1]=0;
    Q.insert(mp(0,1));
    while(!Q.empty())
    {
        val = (*Q.begin()).first, x=(*Q.begin()).second;
        Q.erase(Q.begin());
        for(i=0; i<G[x].size(); i++)
            if(d[G[x][i]] > val+C[x][i])
            {
                d[G[x][i]] = val+C[x][i];
                t[G[x][i]] = x;
                Q.insert(mp(d[G[x][i]],G[x][i]));
            }
    }
}

int main()
{
    freopen("dijkstra.out", "w", stdout);
    citire();
    dijkstra();
    for(int i=2; i<=n;i++)
        if(d[i]==INFI)
            printf("0 ");
        else
            printf("%d ", d[i]);
    return 0;
}