#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;
struct Muchii {
    bool operator() (pair<int, int> a, pair<int, int> b) {
        return a.second > b.second;
    }
};
const int NMAX = 50000, INF = 1 << 30;
int dist[NMAX + 5], viz[NMAX + 5];
int n, m, x, y, i, c;
vector <pair<int, int>> g[NMAX + 5];
priority_queue<pair<int, int>, vector<pair<int, int>>, Muchii> q;
void Dijkstra();
int main() {
    ifstream cin("dijkstra.in");
    ofstream cout("dijkstra.out");
    cin >> n >> m;
    
    for(i = 1; i <= m; ++i) {
        cin >> x >> y >> c;
        g[x].push_back(make_pair(y, c));
    }
    
    Dijkstra();
    
    for(i = 2; i <= n; ++i) {
        if(dist[i] == INF)
            dist[i] = 0;
        cout << dist[i] << " ";
    }
    cout << "\n";
    return 0;
}
void Dijkstra() {
    
    for(i = 1; i <= n; ++i)
        dist[i] = INF;
    
    dist[1] = 0;
    q.push(make_pair(1, 0));
    
    while (!q.empty()) {
        pair<int, int> front = q.top();
        q.pop();
        vector<pair<int, int>>::iterator it;
        if(!viz[front.first]) {
            for(it = g[front.first].begin(); it != g[front.first].end(); ++it) {
                pair<int, int> a = *it;
                if(dist[a.first] > dist[front.first] + a.second) {
                    dist[a.first] = dist[front.first] + a.second;
                    q.push(make_pair(a.first, dist[a.first]));
                }
            }
        }
        viz[front.first] = 1;
    }
}