#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <queue>
int inf = 1<<29;
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m,a,b,c;
vector<pair<int,int> > date[50001];
int distante[50001];
bool viz[50001];

typedef struct comp{
    bool operator()(const pair<int,int> &a,const pair<int,int> &b){
    return distante[a.first] > distante[b.first];}
}comp;

void citire(void){
    f>>n>>m;
    for(int i=1;i<=m;i++){
        f>>a>>b>>c;
        date[a].push_back(make_pair(b,c));}
    for(int i=1;i<=n;i++)
        viz[i]=false;
}
void dijkstra(void){
    priority_queue<pair<int,int>, vector<pair<int,int> >, comp> pq;
    for(int i=2;i<=n;i++)
        distante[i] = inf;
    distante[1]=0;
    pq.push(make_pair(1,0));
    while(!pq.empty()){
        int c=pq.top().first;
        viz[c] = true;
        pq.pop();
        for(unsigned int i=0;i<date[c].size();i++){
        if(!(viz[date[c][i].first])){
            viz[date[c][i].first] = true;
            if(distante[date[c][i].first] > date[c][i].second + distante[c]){
                distante[date[c][i].first] = date[c][i].second + distante[c];
                pq.push(date[c][i]);
                }
                }
    }}
    for(int i=2;i<=n;i++)
    {
        if(distante[i] == inf)
            g<<"0 ";
        else
            g<<distante[i]<<' ';
    }
}
int main()
{
    citire();
    dijkstra();
    cout<<"Finished";
    return 0;
}