#include <bits/stdc++.h>
#define pii pair<int, int>

using namespace std;

bool v[50005]; //visited
long long d[50005]; //distance

vector<pii> a[50005];

vector<pii> q;

//first = to
//second = length

int cmp(pii XX, pii YY) {
    if(XX.second == YY.second)
        return XX.first < YY.first;
    return XX.second < YY.second;
}

struct comp {
    bool operator()(pii XX, pii YY) {
        if(XX.second == YY.second)
            return XX.first < YY.first;
        return XX.second < YY.second;
    }
};

int main()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= m; i ++) {
        int from, to, length;
        cin >> from >> to >> length;
        a[from].push_back(make_pair(to, length));
    }
    /*for(int i = 1; i <= n; i ++) {
        sort(a[i].begin(), a[i].end(), cmp);
    }*/

    int s = 1; //source
    q.push_back(make_pair(s, 0));
    while(!q.empty()) {
        pii cur = q.front();
        q[0] = q[q.size() - 1];
        q.pop_back();
        make_heap(q.begin(), q.end(), comp());
        int cpos = cur.first;
        for(auto x : a[cpos]) {
            if(!v[x.first] || d[x.first] > d[cpos] + x.second) {
                v[x.first] = true;
                d[x.first] = d[cpos] + x.second;
                q.push_back(make_pair(x.first, d[x.first]));
                make_heap(q.begin(), q.end(), comp());
            }
        }
    }
    for(int i = 2; i <= n; i ++)
        cout << d[i] << " ";
    cout << "\n";
    return 0;
}