#include <bits/stdc++.h>
#define cst first
#define nod second

using namespace std;

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

int n,m;
int cost[50005];
int viz[50005];
vector < pair <int,int> > mv[50005];
priority_queue < pair <int,int>, vector < pair <int,int> >, greater < pair<int,int> > > q;

void dijkstra(){
    int i,vecin;
    pair <int,int> x;

    cost[1]=0;
    q.push(make_pair(0,1));

    while(!q.empty()){
        x=q.top();
        vecin=x.nod;
        q.pop();

        if(viz[vecin])
            continue;
        viz[vecin]=1;

        for(i=0;i<mv[vecin].size();i++)
            if(cost[mv[vecin][i].nod]>cost[vecin]+mv[vecin][i].cst){
                cost[mv[vecin][i].nod]=cost[vecin]+mv[vecin][i].cst;
                q.push(make_pair(cost[mv[vecin][i].nod],mv[vecin][i].nod));
            }
    }
}

int main(){
    int i,x,y,c;

    fin>>n>>m;

    for(i=1;i<=n;i++)
        cost[i]=1000000000;

    for(i=1;i<=m;i++){
        fin>>x>>y>>c;
        mv[x].push_back(make_pair(c,y));
    }

    dijkstra();

    for(i=2;i<=n;i++)
        if(cost[i]==1000000000)
            fout<<0<<" ";
        else
            fout<<cost[i]<<" ";

	return 0;
}