#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <set>

#define N 50005
#define INF 0x3f3f3f3f

using namespace std;

int main()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);

    vector <pair<int,int>> g[N];
    int n,m,x,y,c;
    int d[N];
    set<pair<int,int>> q;

    scanf("%d%d", &n,&m);
    for(int i = 0; i < m; ++i){
        scanf("%d%d%d", &x,&y,&c);
        g[x].push_back({y,c});
    }

    memset(d,INF,sizeof(d));
    d[1] = 0;

    q.insert({0,1});
    while(!q.empty()){
        int nod = q.begin()->second;
        q.erase(q.begin());
        for(auto i : g[nod])
            if(d[i.first]>d[nod]+i.second){
                d[i.first] = d[nod]+i.second;
                q.insert({d[i.first],i.first});
            }
    }

    for(int i = 2; i <= n; ++i)
        if(d[i]!=INF)
            printf("%d ", d[i]);
        else
            printf("0 ");

    return 0;
}