#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#define INF (1<<30)
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
int n,m,i,x,y,c,v[50005],d[50005];
vector < pair < int, int > > A[500005];

struct compar
{
    bool operator()( int x, int y){
        return d[x]>d[y];
    }
};

 priority_queue <int , vector <int> , compar > q;

void citire(){
    in>>n>>m;
    for(i=1;i<=m;i++){
        in>>x>>y>>c;
        A[x].push_back(make_pair(y,c));
    }

}

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


        }


    }


}

void afiseaza ()
{
    int i;
    for (i=2;i<=n;i++)
        if (d[i]!=INF)
            out<<d[i]<<" ";
        else out<<"0 ";
    out<<"\n";
}
int main()
{
    citire();
    Dij(1);
    afiseaza();
    return 0;
}