#include <bits/stdc++.h>

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
vector<vector<pair<int, int> > > G;
priority_queue<pair<int,int> > Q;

int N, M;
int DP[100005];
const int INF = 0x3f3f3f3f;

void read()
{
    fin >> N >> M;
    G.resize(N + 1);
    for (int i = 1; i <= M; ++i) {
        int a, b, c;
        fin >> a >> b >> c;
        G[a].emplace_back(c, b);
    }
}

void dijkstra(int k)
{
    memset(DP, INF, sizeof(DP));
    DP[k] = 0;

    Q.push({-DP[k], k});

    while (!Q.empty()) {
        pair<int,int> crt = Q.top();
        Q.pop();

        if (-crt.first != DP[crt.second])
            continue;

        k = crt.second;

        for (auto it : G[k]) {
            ///cerr << it.first << " "  << it.second << "\n";
            if(DP[it.second] > DP[k] + it.first) {
                DP[it.second] = DP[k] + it.first;
                Q.push({-DP[it.second], it.second});
            }
        }
    }

    for (int i = 2; i <= N; ++i) {
        if (DP[i] >= INF) {
            DP[i] = 0;
        }
        fout << DP[i] << " ";
    }
}

int main()
{
    fin.sync_with_stdio(false);
    fin.tie(0);

    read();
    dijkstra(1);

    return 0;
}