#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define NMAX 50005
#define INF 999999999
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
vector<vector<pair<int, int> > > gr;
int N, M;
int d[NMAX];
void read() {
    fin >> N >> M;
    gr.resize(N + 1);
    int x, y, z;
    for (int i = 0; i < M; ++i) {
        fin >> x >> y >> z;
        gr[x].emplace_back(y, z);
    }
}
void setDistances() {
    for (int i = 1; i <= N; ++i) {
        d[i] = INF;
    }
}
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
void dijkstra(int node) {
    d[node] = 0;
    q.emplace(0, node);
    while (!q.empty()) {
        pair<int, int> p = q.top();
        q.pop();
        node = p.second;
        if (d[node] > p.first)
            d[node] = p.first;
        for (pair<int, int> i : gr[node]) {
            if (p.first + i.second < d[i.first]) {
                q.emplace(p.first + i.second, i.first);
            }
        }
    }
}
void afis() {
    for (int i = 2; i <= N; ++i) {
        if (d[i] == INF) {
            fout << 0 << " ";
        }
        else {
            fout << d[i] << " ";
        }
    }
    fout << "\n";
}
int main()
{
    read();
    setDistances();
    dijkstra(1);
    afis();
    return 0;
}