#include <iostream>
#include <set>
#include <vector>

using namespace std;

const int MAXN = 50005;
const int MAXM = 250005;
const int INF = (1 << 31) - 1;

vector<int> graf[MAXN];
vector<int> cost[MAXM];
int dist[MAXN];
int n, m;
int main()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);

    scanf("%d %d\n", &n, &m);
    int from, to, cst;
    for(int i = 0; i < m; ++i){
        scanf("%d %d %d", &from, &to, &cst);
        graf[from].push_back(to);
        cost[from].push_back(cst);
    }
    set<pair<int, int> > heapSimulator;
    heapSimulator.insert(make_pair(0, 1));
    for(int i = 2; i <= n; ++i)
        dist[i] = INF;
    while(heapSimulator.size() != 0){
        int nod = (*heapSimulator.begin()).second;
        int dst = (*heapSimulator.begin()).first;
        heapSimulator.erase(make_pair(dst, nod));
        for(int i = 0; i < graf[nod].size(); ++i){
            if(dist[graf[nod][i]] > dst + cost[nod][i]){
                dist[graf[nod][i]] = dst + cost[nod][i];
                heapSimulator.insert(make_pair(dist[graf[nod][i]],graf[nod][i]));
            }
        }
    }
    for(int i = 2; i <= n; ++i){
        printf("%d ", dist[i]);
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}