#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];

deque<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;
}

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.pop_front();
        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]));
            }
        }
    }
    for(int i = 2; i <= n; i ++)
        cout << d[i] << " ";
    cout << "\n";
    return 0;
}