#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> node;
vector<node>G[50001];

int main()
{
    int i, n, m, u, v, cost, s, current_dist, j;
    freopen("dijkstra.in","r", stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d%d", &n, &m);
    for(i = 1; i <= m; ++i){
        scanf("%d%d%d", &u, &v, &cost);
        G[u].push_back(node(v, cost));
    }

    s = 1;
    vector<int> dist(n+1, INF);
    dist[s] = 0;
    priority_queue< node, vector<node>, greater<node> > pq;
    pq.push(node(0, s));

    while(!pq.empty()){

        node top = pq.top();
        pq.pop();
        int d = top.first, current_node = top.second;

        if(d > dist[current_node]){
            continue;
        }

        for(j = 0; j < (int)G[current_node].size(); ++j){
            v = G[current_node][j].first;
            current_dist = G[current_node][j].second;

            if(dist[current_node] + current_dist < dist[v]){
                dist[v] = dist[current_node] + current_dist;
                pq.push(node(dist[v], v));
            }

        }

    }

    for(i = 2; i <= n; ++i){
        if(dist[i] == INF)
            dist[i] = 0;
        printf("%d ", dist[i]);
    }
    return 0;
}