#include<fstream>
#include<set>
#include<utility>
#include<vector>
#include<set>
#define DIM 50003
#define INF 9999999
using namespace std;
int n, m2, i, j, D[50003], m[50003], x, y, z, k, minim, vecin, nrm;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

set<pair<int, int> > S;
vector< pair<int,int> > L[DIM];
int main(){
    in>>n>>m2;
    for(;m2--;){
        in>>x>>y>>z;
        L[x].push_back(make_pair(y, z));
        //L[y].push_back(make_pair(x, z));
    }
    D[1]=0;
    for(i=2; i<=n; i++)
        D[i]=INF;

    S.insert(make_pair(0, 1));

    while(nrm<=n){
        if (S.empty())
            break;

        pair<int, int> p = *S.begin();


        m[ p.second ]=1;
        S.erase( S.begin() );
        k = p.second;

        nrm++;
        for(i=0; i<L[k].size(); i++){
            vecin=L[k][i].first;
            if(D[vecin]>D[k]+L[k][i].second){
                // era in set perechea
                S.erase(make_pair(D[vecin], vecin));
                D[vecin]=D[k]+L[k][i].second;
                S.insert(make_pair(D[vecin], vecin));
                // bag in set perechea (  D[vecin], vecin  )

            }
        }
    }
    for(i=2; i<=n; i++)
        (D[i]!=INF)?(out<<D[i]<<" "):(out<<"0 ");

    return 0;
}