#include <fstream>
#include <queue>
#include <vector>

using namespace std;

struct edge {
    int node;
    int cost;
};
vector < edge > v[50001];
queue < int > q;
int cost[50001];

int main() {
    ifstream in("dijkstra.in");
    ofstream out("dijkstra.out");
    
    int n, m, i, A, B, C, nxt;
    
    in >> n >> m;
    for(i = 1; i <= m; i++) {
        in >> A >> B >> C;
        v[A].push_back({B,C});
    }
    
    cost[1] = 1;
    q.push(1);
    
    while(!q.empty()) {
        nxt = q.front();
        q.pop();
        for(i = 0; i < v[nxt].size(); i++) {
            if(!cost[v[nxt][i].node]) {
                cost[v[nxt][i].node] = cost[nxt] + v[nxt][i].cost;
                q.push(v[nxt][i].node);
            }
            else if(cost[v[nxt][i].node] > cost[nxt] + v[nxt][i].cost) {
                cost[v[nxt][i].node] = cost[nxt] + v[nxt][i].cost;
                q.push(v[nxt][i].node);
            }
        }
    }
    
    for(i = 2; i <= n; i++)
        out << cost[i] -1 << ' ';
    
    return 0;
}