#include<iostream>
#include<fstream>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#include<algorithm>
#include<iomanip>
#include<bitset>
using namespace std;

const int N = 51000;
const int S = 1;
const int inf = 2001000;
const int M = 250100;

int n, m, dist[N], a[M], b[M], c[M];
vector<int> v[N];
priority_queue<pair<int, int> > h;

void dijkstra() {
    int i;

    for(i = 1; i <= n; ++i)
        dist[i] = inf;

    dist[S] = 0;
    h.push(pair<int, int>(0, S));

    while(!h.empty()) {
        int dc = -h.top().first, el = h.top().second;
        h.pop();

        if(dc != dist[el])
            continue;

        for(vector<int>::iterator it = v[el].begin(); it != v[el].end(); ++it) {
            int oth = a[*it] + b[*it] - el;

            if(dist[oth] > dist[el] + c[*it]) {

                dist[oth] = dist[el] + c[*it];
                h.push(pair<int, int>(-dist[oth], oth));
            }
        }
    }
}

int main() {
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);

    cin >> n >> m;
    int i;

    for(i = 1; i <= m; ++i) {
        scanf("%d%d%d", &a[i], &b[i], &c[i]);

        v[a[i]].push_back(i);
        //v[b[i]].push_back(i);
    }

    dijkstra();

    for(i = 2; i <= n; ++i) {
        if(dist[i] == inf)
            dist[i] = 0;
        printf("%d ", dist[i]);
    }

    return 0;
}