#include <iostream>
#include <vector>
#include <fstream>
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]<<" ";
}
int main() {
    citire();
    Dijkstra();

    return 0;
}