#include <fstream>
#include <vector>
#include <queue>
#include <climits>
#define INF INT_MAX
using namespace std;
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
vector< pair<int,int> > G[105];
int n,p,D[105],t[105],viz[105],m;
void citire(){
    cin>>n>>m;
    p=1;
    int i,j,x;
    while(cin>>i>>j>>x)
        G[i].push_back(make_pair(j,x));
}
queue<int> coada;
void dijkstra(){
    viz[p]=1;
    vector< pair <int,int> >::iterator it;
    int i;
    for(it=G[p].begin();it!=G[p].end();++it){
        D[it->first]=it->second;
        coada.push(it->first);
        t[it->first]=p;
    }
    for(i=1;i<=n;i++)
        if(D[i]==0){
            D[i]=INF;
            t[i]=0;
        }
    while(!coada.empty()){
        int u=coada.front();
        for(it=G[u].begin();it!=G[u].end();++it)
            if(!viz[it->first])
            if(D[it->first]>D[u]+it->second){
                if(D[it->first]==INF)
                    coada.push(it->first);
                D[it->first]=D[u]+it->second;
                t[it->first]=u;
            }
        viz[u]=1;
        coada.pop();
    }
    for(i=1;i<=n;i++){
        if(i==p)
            ;
        else if(D[i]==INF)
            cout<<0<<' ';
        else
            cout<<D[i]<<' ';
    }
}
void afisare(){
    vector< pair<int,int> >::iterator it;
    int i;
    for(i=1;i<=n;i++){
        for(it=G[i].begin();it!=G[i].end();++it)
            cout<<i<<' '<<it->first<<' '<<it->second<<'\n';
    }
}
int main(){
    citire();
    dijkstra();
    //afisare();
    return 0;
}