#include <bits/stdc++.h>
#define INF 2000000000

using namespace std;

ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");

vector < pair < int, int > > a[50005];
int n;

void dijkstra()
{
    vector < int > d(n + 1, INF);
    vector < int > ans(n + 1);
    int lg = 0;
    multiset < pair < int, int > > s;
    d[1] = 0;
    s.insert({0, 1});
    while(!s.empty()) {
        int v = s.begin() -> second;
        lg += s.begin() -> first;
        ans[v] = lg;
        s.erase(s.begin());
        for(auto x : a[v]) {
            int to = x.first, len = x.second;
            if(d[v] + len < d[to]) {
                s.erase({d[to], to});
                d[to] = d[v] + len;
                s.insert({d[to], to});
            }
        }
    }
    for(int i = 2; i <= n; ++i) fout << d[i] << " ";
}
int main()
{
    ios::sync_with_stdio(false);
    fin.tie(0);
    int m;
    fin >> n >> m;
    for(int i = 1; i <= m; ++i) {
        int x, y, w;
        fin >> x >> y >> w;
        a[x].push_back(make_pair(y, w));
    }
    dijkstra();
    return 0;
}