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

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

const int NMAX = 50001;
const int MMAX = 250001;
const int INF = (NMAX-1)*20001;
struct muchie
{
    int nod,cost;
};
int N,M;
vector< vector<muchie> > G(NMAX);
void citire()
{
    fin>>N>>M;
    int x,y,c;
    for(int i=0;i<M;i++)
    {
        fin>>x>>y>>c;
        muchie m;
        m.nod=y-1;
        m.cost = c;
        G[x-1].push_back(m);
    }
}
void Dijkstra()
{
    vector<int> viz(N,0);
    vector<int> d(N);

    for(int i=0;i<N;i++)
         d[i]=INF;
    d[0]=0;
    for(int i=0;i<N;i++)
    {
        int index=-1,min=INF;
        for(int j=0;j<N;j++)
            if(d[j]<min && !viz[j]) {
                min = d[j];
                index = j;
            }
        for(auto edge:G[index])
            if(d[index]+edge.cost < d[edge.nod])
                d[edge.nod]=d[index]+edge.cost;
        viz[index]=1;
    }
    for(int i=1;i<N;i++)
        fout<<d[i]<<" ";
}
void Dijkstra2()
{
    set <pair<int,int>> S;
    vector<int> d(N,INF);
    d[0]=0;
    S.insert(make_pair(0,0));
    for(int i=0;i<N;i++)
    {
        int index = (*S.begin()).second;
        for(auto edge:G[index])
            if(d[index] + edge.cost < d[edge.nod])
            {
                S.erase(make_pair(d[edge.cost],edge.nod));
                d[edge.nod]= d[index]+edge.cost;
                S.insert(make_pair(d[edge.cost],edge.nod));
            }
        S.erase(S.begin());
    }
    for(int i=1;i<N;i++)
          if(d[i]== INF) fout<<0<<" ";
          else fout<<d[i]<<" ";
}
int main() {
    citire();
    Dijkstra2();

    return 0;
}