#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <utility>
#define NMAX 50001
#define INF 1000000000
using namespace std;

int N,M;
int d[NMAX];
vector < pair<int,int> > G[NMAX];
ofstream fout("dijkstra.out");

class Comparator{
public:
    bool operator()(const int& x,const int& y)
    {return d[x]>d[y];}

};
priority_queue<int, vector<int>, Comparator> PQ;

void dijkstra()
{
    int vf,i;
    for(i=1;i<=N;i++)
        d[i]=INF;

    d[1]=0;
    PQ.push(1);
    while(!PQ.empty())
    {
        vf=PQ.top();
        PQ.pop();
        for(i=0;i<G[vf].size();i++)//parcurg vecinii lui vf
            if(d[G[vf][i].first]>d[vf]+G[vf][i].second)
            {
                d[G[vf][i].first]=d[vf]+G[vf][i].second;
                PQ.push(G[vf][i].first);
            }
    }
}

int main()
{
    int i,x,y,c;
    ifstream fin("dijkstra.in");
    fin>>N>>M;
    for(i=0;i<M;i++)
    {
        fin>>x>>y>>c;
        G[x].push_back(make_pair(y,c));
    }
    fin.close();

    dijkstra();


    for(i=2;i<=N;i++)
        if(d[i]==INF) fout<<0<<" ";
            else fout<<d[i]<<" ";
    fout.close();
    return 0;
}