#include <bits/stdc++.h>

using namespace std;
const int INF = 0x3f3f3f3f;
const int Nmax = 60005;
vector<pair<int,int> > G[Nmax];
int DP[Nmax];
priority_queue<pair<int,int> > Q;
int N, M;

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


void dijkstra(int k)
{
    memset(DP, INF, sizeof(DP));
    DP[k] = 0;
    Q.push({0,k});
    while(!Q.empty()) {
        auto crt = Q.top();
        Q.pop();
        int cost = -crt.first;
        k = crt.second;
        if(DP[k] != cost)
            continue;
        for(auto it : G[k])
            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)
            cout << 0 << " ";
        else
            cout << DP[i] << " ";
    }
    cout << "\n";
}

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

    read();
    dijkstra(1);

    return 0;
}