#include <bits/stdc++.h>
#define NMAX 50005
#define INF 2e9
using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int n, m, x, y, pas, path[NMAX];
vector < pair< int, int > > nod[NMAX];
priority_queue < pair< int, int > > q;

void read(){
    f>>n>>m;
    for(int i = 1; i <= m; ++i){
        f>>x>>y>>pas;
        nod[x].push_back(make_pair(y, pas));
    }
}

void dijkstra(int node){
    int cost, next_node;
    for(int i = 2; i <= n; ++i)
        path[i] = INF;
    path[node] = 0;
    q.push({0, node});
    while(!q.empty()){
        next_node = q.top().second;
        cost = -q.top().first;
        q.pop();
        if(path[next_node] != INF && path[next_node] != 0)
            continue;
        path[next_node] = cost;
        for(auto it:nod[next_node])
            if(path[it.first] > cost + it.second)
                q.push({-(cost+it.second), it.first});

    }
}

int main()
{
    read();
    dijkstra(1);
    for(int i = 2; i <= n; ++i)
        g<<path[i]<<' ';
    g.close();
    return 0;
}