#include <fstream>
#include <vector>
#include <queue>
 
using namespace std;
 
const int N = 50001;
const int INF = 1000000000;
 
struct muchie {
    int vf, cst;
};
 
int n, m;
bool sel[N];
vector <muchie> a[N];
priority_queue <pair<int, int>> h;
int d[N];
 
void citire() {
    int x, y, c;
    ifstream in("dijkstra.in");
    in >> n >> m;
    for (int i = 0; i < m; i++) {
        in >> x >> y >> c;
        a[x].push_back((muchie){y, c});
    }
    in.close();
}
 
void dijkstra(int x0) {
    int x, y, c;
    d[x0] = 0;
    h.push(make_pair(-d[x0], x0));
    for (int i = 2; i <= n; i++) { 
        d[i] = INF;
        h.push(make_pair(-d[i], i));
    }
    while (!h.empty()) {
        while (!h.empty() && sel[h.top().second]) {
            h.pop();
        }
        if (!h.empty()) {
            x = h.top().second;
            sel[x] = true;
            for (int i = 0; i < a[x].size(); i++) {
                y = a[x][i].vf;
                c = a[x][i].cst;
                if (d[x] + c < d[y]) {
                    d[y] = d[x] + c;
                    h.push(make_pair(-d[y], y));
                }
            }
        }
    }
}
 
void afisare() {
    ofstream out("dijkstra.out");
    for (int i = 2; i <= n; i++) {
        out << (d[i] == INF ? 0 : d[i]) << " ";
    }
    out.close();
}
 
int main() {
    citire();
    dijkstra(1);
    afisare();
    return 0;
}