#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
const int NMax = 50000;
const int oo = 50000;
vector < pair <int, int> > G[NMax + 5];
int N,M,D[NMax + 5];

queue <int> Q[oo + 5];

void Read()
{
  fin >> N >> M;
  for(int i = 1; i <= M; ++i)
  {
    int x,y,c;
    fin >> x >> y >> c;
    G[x].push_back(make_pair(y,c));
  }
}

void Solve()
{
  for(int i = 2; i <= N; ++i)
   {
      D[i] = oo;
      Q[oo].push(i);
   }
  Q[0].push(1);

  for(int i = 0; i <= oo; ++i)
  {
    while(!Q[i].empty())
    {
      int Nod = Q[i].front(); Q[i].pop();
      if(D[Nod] != i) continue;
      for(int j = 0; j < (int)G[Nod].size(); ++j)
      {
        int Vecin = G[Nod][j].first, Cost = G[Nod][j].second;
        if(D[Vecin] > D[Nod] + Cost)
        {
          D[Vecin] = D[Nod] + Cost;
          Q[D[Vecin]].push(Vecin);
        }
      }
    }
  }
}

void Print()
{
  for(int i = 2;  i <= N; ++i)
    fout << D[i] << " ";
  fout << "\n";
}

int main()
{
    Read();
    Solve();
    Print();
    return 0;
}