#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <climits>
using namespace std;

#define INFINIT INT_MAX

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

struct pereche{
    int varf;int cost;
};

int n,m,D[50001],V[50001];
vector<pereche> EL[50001];
set< pair <int,int> > T; // distanta la x

int main()
{
    fin>>n>>m;
    int a;pereche b;
    for(;m;m--){
        fin>>a>>b.varf>>b.cost;
        EL[a].push_back(b);
    }
    int dist,vecin;
    V[1]=1;
    for(int i=2;i<=n;i++)
        D[i]=INFINIT;
    T.insert(make_pair(0,1));
    while(T.size()>0){
        dist=(*T.begin()).first;
        vecin=(*T.begin()).second;
        T.erase(*T.begin());
        for(int i=0;i<EL[vecin].size();i++)
            if(D[EL[vecin][i].varf]>dist+EL[vecin][i].cost){
                D[EL[vecin][i].varf]=dist+EL[vecin][i].cost;
                T.insert(make_pair(D[EL[vecin][i].varf],EL[vecin][i].varf));
            }
    }
    for(int i=1;i<=n;i++)
        cout<<D[i]<<" ";
    return 0;
}