#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define Nmax 50001
#define oo (1<<31)-1
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int n,m,D[Nmax];
bool InsideQ[Nmax];

vector <pair <int,int> > V[Nmax];

struct CompareDistance
{
    bool operator()(int x,int y)
    {
        return D[x]>D[y];
    }
};
priority_queue < int , vector <int> , CompareDistance >Q;

void read()
{
      f>>n>>m;

     for(int i=1;i<=m;i++)
     {
         int nod1,nod2,cost;
         f>>nod1>>nod2>>cost;
         V[nod1].push_back(make_pair(nod2,cost));
     }
}
void dijkstra(int Nod)
{
     for(int i=1;i<=n;i++)D[i]=oo;

    D[Nod]=0;
    Q.push(Nod);
    InsideQ[Nod]=true;

    while(!Q.empty())
    {
        int CurrentNod=Q.top();
        Q.pop();
        //InsideQ[CurrentNod]=false;

         for(int i=0;i<V[CurrentNod].size();i++)
         {
             int neighbor=V[CurrentNod][i].first;
             int cost=V[CurrentNod][i].second;

              if(D[CurrentNod]+cost<D[neighbor])
              {
                  D[neighbor]=D[CurrentNod]+cost;

                   if(InsideQ[neighbor]==false)
                   {
                       Q.push(neighbor);
                       InsideQ[neighbor]=true;
                   }
              }

         }
    }
}

void print()
{
       for(int i=2;i<=n;i++){
        if(D[i]!=oo)g<<D[i]<<" ";
        else g<<"0 ";
    }
}

int main()
{
    read();
    dijkstra(1);
    print();
}