#include <iostream>
#include <fstream>
#include <vector>
#include <string.h>
#include <queue>

using namespace std;

const int MAX = 50002;

vector<int> Djk[MAX];

int Size[MAX],S[MAX],Dst[MAX];

void BFS(int k);

void citire(int &N,int &M);

int main()
{
    int N, M;
    ofstream g("dijkstra.out");

    citire(N,M);
    BFS(1);

    for(int i = 2;i<=N;++i)
        {
        g<<Dst[i]<<" ";
        }
    return 0;
}

void citire(int &N,int &M)
{
     int i,x,y,l;
     fstream f("dijkstra.in",ios::in);
     f>>N>>M;
     for(i=1;i<=M;++i)
        {
        f>>x>>y>>l;
        Djk[x].push_back(y);
        Djk[x].push_back(l);
        }
    for(i=1;i<=N;++i)
        {
        Size[i] = Djk[i].size();
        }
    f.close();
}

void BFS(int k)
{
   memset(Dst,0,sizeof(Dst));

   int L = 1;

   S[L] = k;

   int i,j;

   for(i = 1;i <= L; ++i)
    {
    for(j = 0;j < Size[S[i]];j+=2)
        {
           if(!Dst[Djk[S[i]][j]])
            {
              S[L+1] = Djk[S[i]][j];
              Dst[S[L+1]] = Djk[S[i]][j+1] + Dst[S[i]];
              ++L;
            }
           else
            {
                if( Dst[Djk[S[i]][j]] > ( Djk[S[i]][j+1] + Dst[S[i]]))
                    {
                    Dst[Djk[S[i]][j]]= Djk[S[i]][j+1] + Dst[S[i]];
                    S[L+1] = Djk[S[i]][j];
                    }

            }
        }
    }
}