#include <bits/stdc++.h>

using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
vector<pair<int, int>> graf[50003];
int minim[1000];
priority_queue<pair<int, int>> q;

void dijkstra(int start){
    q.push({0, start});
    minim[start] = 0;

    while(!q.empty()){
        int nod = q.top().second;
        q.pop();
        for(auto &vecin: graf[nod]){
            int nextnod = vecin.first;
            int cost = vecin.second;
            if(minim[nod] + cost < minim[nextnod]){
                minim[nextnod] = cost + minim[nod];
                q.push({-minim[nextnod], nextnod});
            }
        }
    }
}

int main()
{
    int n, m;
    fin>>n>>m;

    for (int i = 1; i <= n; i++)
        minim[i] = 1e9;

    for (int i = 1; i <= m; i++) {
        int x, y, z;
        fin >> x >> y >> z;
        graf[x].push_back({y, z});
    }
    dijkstra(1);
    for(int i=2; i<=n; i++){
        if(minim[i] == 1e9)
            fout<<0<<' ';
        else
            fout<<minim[i]<<' ';
    }
}