#include <fstream>
#include <vector>
#include <queue>
#define maxn 50001
#define oo 1<<30
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
int n,m,i,j,x,y,c;
vector <int> d(maxn,oo);
struct arc{int x , cost;};
struct cmp{
    bool operator()( int a, int b ){
        if(d[a]>d[b]) return 1;
        return 0;
    }
};
vector <arc> l[maxn];
priority_queue < int , vector < int > , cmp > q;
int main(){
    in >>n>>m;
    for (i=1;i<=m;++i){
        in>>x>>y>>c;
        l[x].push_back((arc){y,c});
    }
    d[1]=0;
    q.push(1);
    vector <arc> :: iterator it,sf;
    while ( !q.empty() ){
        x = q.top();
        q.pop();
        it=l[x].begin();
        sf=l[x].end();
        for (;it!=sf;++it){
            if (d[x]+(*it).cost < d[(*it).x]){
                d[(*it).x]=d[x]+(*it).cost;
                q.push((*it).x);
            }
        }
    }
    for (i=2;i<=n;++i )
    {
        if (d[i] != oo )
            out<<d[i]<<' ';
        else
            out<<"0 ";
    }
    out << '\n'; out.close();
    return 0;
}