#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const int dim=5e4+5,inf=1e9;
int n,m,d[dim],viz[dim];
vector<pair<int,int> > G[dim];
void dijkstra(int p){
    viz[p]=1;
    for(int i=1;i<n;i++){
        int mic,mn=inf;
        for(int j=1;j<=n;j++){
            if(d[j]<mn and !viz[j]){
                mn=d[j];
                mic=j;
            }
        }
        if(mn==inf){
            break;
        }
        viz[mic]=1;
        for(int j=0;j<G[mic].size();j++){
            pair<int,int> x=G[mic][j];
            if(d[x.first]>d[mic]+x.second){
                d[x.first]=d[mic]+x.second;
            }
        }
    }
}
int main(){
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    f>>n>>m;
    for(int i=2;i<=n;i++){
        d[i]=inf;
    }
    for(int i=1;i<=m;i++){
        int x,y,c;
        f>>x>>y>>c;
        G[x].push_back({y,c});
        if(x==1){
            d[y]=c;
        }
    }
    dijkstra(1);
    for(int i=2;i<=n;i++){
        if(d[i]==inf){
            g<<0<<' ';
        }
        else{
            g<<d[i]<<' ';
        }
    }
    return 0;
}