#include<fstream>
#include<vector>
#include<deque>
#define oo 1<<27
#define nmax 50005
using namespace std;
struct arc{int nod,cost;};
vector<arc> l[nmax];
vector<int> d(nmax,oo);
deque<int> q;
int acum,n,m,x,y,c;
int main(){
    ifstream in("dijkstra.in"); ofstream out("dijkstra.out");
    in>>n>>m;
    for(int i=1;i<=m;++i) { in>>x>>y>>c; l[x].push_back((arc){y,c});}
    d[1]=0; q.push_back(1);
    while(!q.empty()){
        acum=q.front(); q.pop_front();
        vector<arc> :: iterator it=l[acum].begin(), sf=l[acum].end();
        for(;it!=sf;++it){
            if( d[(*it).nod]>d[acum]+(*it).cost){
                d[(*it).nod]=d[acum]+(*it).cost;
                q.push_back((*it).nod);
            }
        }
    }
    for(int i=2;i<=n;++i){
        if(d[i]==oo) out<<"0 ";
        else out<<d[i]<<' ';
    }
    out<<'\n'; out.close(); return 0;
}