#include <fstream>
#include <queue>

using namespace std;

ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");

struct Alex {
    int y, c;
    bool operator < (const Alex aux) const {
        return c > aux.c;
    }
};

const int NMAX = 5e4, INF = (1 << 30);
priority_queue<Alex, vector<Alex>> q;
vector<Alex> g[NMAX + 2];
int n, m, x, y, c;
int dist[NMAX + 2], viz[NMAX + 2];

int main() {
    cin >> n >> m;
    for(int i = 1; i <= m; ++i) {
        cin >> x >> y >> c;
        g[x].push_back({y, c});
    }
    
    for(int i = 1; i <= n; ++i)
        dist[i] = INF;
    dist[1] = 0;
    q.push({1, 0});
    
    while (!q.empty()) {
        Alex fr = q.top();
        q.pop();
        if(!viz[fr.y]) {
            for(auto it: g[fr.y]) {
                if(dist[it.y] > dist[fr.y] + it.c) {
                    dist[it.y] = dist[fr.y] + it.c;
                    q.push({it.y, dist[it.y]});
                }
                
            }
        }
        
        viz[fr.y] = 1;
    }
    
    for(int i = 2; i <= n; ++i) {
        if(dist[i] == INF)
            dist[i] = 0;
        cout << dist[i] << " ";
    }
    return 0;
}