#include<fstream>
#include<vector>
#include <queue>

using namespace std;

ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");


int n,m,x,y,z;
bool viz[50001];
int d[50001];
vector<pair<int,int> >mm[50001];

void solve(int x){
    for(int i=1;i<=n;i++)
        d[i]=2e9;
    priority_queue<pair<int, int> > md;
    d[x]=0;
    md.push({0,x});
    while(md.size()>0){
        int asta=md.top().second;
        md.pop();
        if(viz[asta]!=true){
            viz[asta]=true;
            for(int i=0;i<mm[asta].size();i++){
                int asta2=mm[asta][i].first;
                int cost=mm[asta][i].second;
                if(d[asta2]>d[asta]+cost){
                    d[asta2]=d[asta]+cost;
                    md.push({-d[asta2],asta2});
                }
            }
        }
    }
}

int main () {
cin>>n>>m;
for(int i=1;i<=m;i++){
    cin>>x>>y>>z;
    mm[x].push_back(make_pair(y,z));
}
solve(1);
for(int i=2;i<=n;i++)
    if(d[i]<2e9)
        cout<<d[i]<<" ";
    else
        cout<<0<<" ";
    return 0;
}