#include <iostream>
#include <fstream>
#include <queue>
#define N 50005
#define inf 1e7
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n, m;
vector < pair <int, int> > a[N];
bool viz[N];
int dist[N];
queue <int> q;
void Bellman(int nod) {
    for(int i = 1; i <= n; ++i)
        dist[i] = inf;
    dist[nod] = 0;
    q.push(nod);
    viz[nod] = true;
    while(!q.empty()) {
        int val = q.front();
        q.pop();
        viz[val] = false;
        for(auto i : a[val])
            if(dist[val] + i.second < dist[i.first]) {
                dist[i.first] = dist[val] + i.second;
                if(viz[i.first] == 0) {
                    viz[i.first] = 1;
                    q.push(i.first);
                }
            }
    }
}
int main() {
    f >> n >> m;
    int x, y, c;
    for(int i = 1; i <= m; ++i) {
        f >> x >> y >> c;
        a[x].push_back({y, c});
    }
    Bellman(1);
    for(int i = 2; i <= n; ++i)
        if(dist[i] != inf)
            g << dist[i] << ' ';
        else
            g << 0 << ' ';
    return 0;
}