#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>

using namespace std;

#define v1 vector<pair<int,int> >

const int inf=100000;

v1 *muchii;
v1 h;
int *distante;
int *viz;

int main()
{
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");

    long long n,m;
    int x,y,c;


    f>>n>>m;

    muchii= new v1[n+1];
    distante=new int[n+1];
    viz=new int[n+1];

    distante[1]=0;
    for(int i=2;i<n+1;i++){
        distante[i]=inf;
        viz[i]=0;
    }

    for(int i=0;i<m;i++){
        f>>x>>y>>c;
        muchii[x].push_back(make_pair(y,c));
        //muchii[y].push_back(make_pair(x,c));
    }

    //distante[1]=0;
    h.push_back(make_pair(0,1));
    make_heap(h.begin(),h.end());

    while(!h.empty()){
        int c;
        pair<int,int > p;
        p=h.front();
        pop_heap(h.begin(),h.end());
        h.pop_back();

        c=-p.first;

        if(viz[p.second]==0){
            viz[p.second]=1;
            for(v1::iterator i=muchii[p.second].begin();i<muchii[p.second].end();++i){
                if(c+(*i).second<distante[(*i).first]){
                    distante[(*i).first]=c+(*i).second;
                    h.push_back(make_pair(-distante[(*i).first],(*i).first));
                    push_heap(h.begin(),h.end());
                }
            }
        }

    }

    for(int i=2;i<n+1;i++){
        if(distante[i]==inf) g<<0<<" ";
        else
        g<<distante[i]<<" ";
    }

    return 0;
}