#include <fstream>
#include <queue>
#include <vector>
#define INF 200000000

using namespace std;

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

int N,M;

struct Nod
{
  vector <int> Ad;
  vector <int> Cost;
} G[50002];

int dist[50002];

void Read()
{
  fin>>N>>M;

  int a,b,d;

  for(int i=1; i<=M; ++i)
  {
    fin>>a>>b>>d;

    G[a].Ad.push_back(b);
    G[a].Cost.push_back(d);
  }

  fin.close();
}

void Dijkstra()
{
  priority_queue< pair<int,int>, vector<pair <int,int> >, greater<pair<int,int> > > Heap;

  pair<int,int> aux;

  aux.first=0;
  aux.second=1;

  Heap.push(aux);

  /*for(int i=2; i<=N; ++i)
  {
    aux.first=INF;
    aux.second=i;

    Heap.push(aux);
  }*/

  for(int i=2; i<=N; ++i)
    dist[i]=INF;

  dist[1]=0;

  int nod_curent;
  int dist_curenta;
/*
  while(!Heap.empty())
  {
    fout<<Heap.top().second<<' ';

    Heap.pop();
  }*/


  while(!Heap.empty())
  {
    nod_curent=Heap.top().second;

    Heap.pop();

    //fout<<nod_curent<<' ';

    for(int i=0; i<G[nod_curent].Ad.size(); ++i)
      if(dist[G[nod_curent].Ad[i]]>dist[nod_curent]+G[nod_curent].Cost[i])
       {
         dist[G[nod_curent].Ad[i]]=dist[nod_curent]+G[nod_curent].Cost[i];

         aux.first=dist[G[nod_curent].Ad[i]];
         aux.second=G[nod_curent].Ad[i];

         Heap.push(aux);
       }
  }
}

void Print()
{
  for(int i=2; i<=N; ++i)
    if(dist[i]<INF) fout<<dist[i]<<' ';
    else fout<<'0'<<' ';
}

int main()
{
    Read();
    Dijkstra();
    Print();

    return 0;
}