#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#include <queue>

#define MAX 100001
#define INF 0x3f3f3f3f

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



class Graf{
    public:
    //liste de adiacenta cu costuri
        vector< vector<pair<int, int> > >A;

        //nr noduri
        int mN, mM;
        //vector pt drumurile minime
        vector<int> D;
        //multimea nodurilor pt care inca n am calculat durmul  minim
        vector <int> F;



        //constructor

        Graf(int N, int M){
            mN = N;
            mM = M;
            //fac marimea de N
            D.resize(mN+1);
            F.resize(mN + 1);
            //pregatesc lista pt N noduri
            A.resize(mN+1);
        }

        void CitireG(int M);
        void Dijkstra(int s);

};


void Graf:: CitireG(int M){

    int x,y,c;

    for(int i = 0; i < M; i++){

        fin >> x >> y >> c;
        A[x].push_back(make_pair(y,c));
    }

    //nodul sursa e 1
    for(int i = 1 ; i <= mN; i++)
        D[i] = INF;


}
void Graf ::Dijkstra(int x)
{
  int i;
  for (i = 1; i <= mN; i++)
    D[i] = INF;
  D[x] = 0;
  priority_queue<pair<int, int> > q;
  q.push(make_pair(0, x));
  while (!q.empty())
  {
    int nod = q.top().second;
    q.pop();
    if (!F[nod] ){
        F[nod] = true;
        for (auto curr : A[nod])
        {
            if (D[nod] + curr.second < D[curr.first])
            {
                D[curr.first] = D[nod] + curr.second;
                q.push(make_pair(-D[curr.first], curr.first));
            }
        }
    }
  }
  for (i = 2; i <= mN; i++)
    if (D[i] != INF)
      fout <<D[i]<<" ";
    else fout<<0<<" ";
}



int main(){
    int N, M;
    fin >> N >> M;
    Graf G(N,M);
    G.CitireG(M);
    G.Dijkstra(1);



    return 0;
}