#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];
bool v[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();
}

struct Pair
{
  int dist;
  int nod;
};

struct comp
{
  bool operator()(const Pair &X,const Pair &Y)
  {
    return X.dist>Y.dist;
  }
};

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

   dist[1]=0;

   priority_queue <Pair,vector<Pair>,comp> Heap;

   Pair aux;

   aux.dist=0;
   aux.nod=1;

   Heap.push(aux);

   int nod_curent;

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

      if(v[nod_curent]) continue;
      else v[nod_curent]=1;

      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.dist=dist[G[nod_curent].Ad[i]];
           aux.nod=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;
}