#include <bits/stdc++.h>

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

vector<pair<int,int>> G[50005];
priority_queue<pair<int,int>> Q;
int viz[50005],val[50005];
int n,m;

void dijkstra(int nod){
    int i,top,valtop,cost,vecin;
    for(i = 1; i <= n; i++){
        val[i] = INT_MAX-5;
    }
    val[nod] = 0;
    Q.push(make_pair(0,nod));

    while(!Q.empty()){
        top = Q.top().second; valtop = -Q.top().first;
        Q.pop();
        if(viz[top] == 1){
            continue;
        }
        viz[top] = 1;

        for(i = 0; i < G[top].size(); i++){
            vecin = G[top][i].first;
            cost = G[top][i].second;
            if(valtop + cost < val[vecin]){
                val[vecin] = valtop+cost;
                Q.push(make_pair(-val[vecin],vecin));
            }
        }
    }
    for(i = 2; i <= n; i++){
        if(val[i] == INT_MAX-5){
            val[i] = 0;
        }
        fout<<val[i]<<' ';
    }
}

int main()
{
    int i,a,b,c;
    fin>>n>>m;
    for(i = 1; i <= m; i++){
        fin>>a>>b>>c;
        G[a].push_back(make_pair(b,c)); //first = vecin, second = cost;
    }
    dijkstra(1);
    return 0;
}