#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define maxi 50005
#define INF (1<<30)
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
vector < pair <int , int> > v[maxi];
int d[maxi];
bool viz[maxi];
int n,m,i,x,y,c;
struct comp{
    bool operator()(int x, int y){
        return d[x]>d[y];
    }

};
priority_queue<int , vector <int> , comp> q;

void dij(int sursa){
    for(i=1;i<=n;++i){
        d[i]=INF;
    }
    d[sursa]=0;
    viz[sursa]=1;
    q.push(sursa);
    while(!q.empty()){
    int nodcurent=q.top();
    q.pop();
    viz[nodcurent]=false;
    vector < pair <int, int> > ::iterator it;
    for(it=v[nodcurent].begin() ; it!=v[nodcurent].end() ; ++it){
        int vecin=it->first;
        int cost=it->second;
        if(d[vecin]>d[nodcurent]+cost){
            d[vecin]=d[nodcurent]+cost;
            if(!viz[vecin]){
                viz[vecin]=true;
                q.push(vecin);
            }
        }
    }


    }
}


int main()
{
    in>>n>>m;
    for(i=1;i<=m;++i){
        in>>x>>y>>c;
        v[x].push_back(make_pair(y,c));
    }
    dij(1);
    for(i=2;i<=n;++i){
        if(d[i]==INF) out<<0<<' ';
        else out<<d[i]<<' ';
    }
    return 0;
}