#include <fstream>
#include <cstring>
#include <vector>
#include <queue>
#define inf 0x3f3f3f3f
#define MAXN 50004
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
struct punct{
    int node, c;
    bool operator < (const punct& other) const {
        return c > other.c;
    }
};
vector <punct> graph[MAXN];
priority_queue <punct> Q;
int cost[MAXN];
inline void Read(int &N, int &M) {
    int x, y, c;
    fin >> N >> M;
    for (int i = 1; i <= M; i++) {
        fin >> x >> y >> c;
        graph[x].push_back({y, c});
    }
}
inline void Dijkstra(int N) {
    int z, cc;
    memset(cost, inf, sizeof(cost));
    Q.push({1, 0});
    cost[1] = 0;
    while (!Q.empty()) {
        z = Q.top().node;
        cc = Q.top().c;
        Q.pop();
        if (cost[z] != cc)
            continue;
        for (auto x : graph[z]) { 
            if (cost[x.node] > cost[z] + x.c) {
                cost[x.node] = cost[z] + x.c;
                Q.push({x.node, cost[x.node]});
            }
        }
    }
}
inline void Write(int N) {
    for (int i = 2; i <= N; i++) {
        if (cost[i] == inf)
            cost[i] = 0;
        fout << cost[i] << " ";
    }
}
int main () {
    int N, M;
    Read(N, M);
    Dijkstra(N);
    Write(N);
}