#include <fstream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

const int NMAX = 50000;

vector <pair <int, int>> graf[1 + NMAX];
queue <int> q;

int costuri[1 + NMAX];

void bfs()
{
  q.push(1);
  while (!q.empty())
  {
    int nod = q.front();
    q.pop();
    for (auto it = graf[nod].begin(); it != graf[nod].end(); it++)
    {
      int vecin = (*it).first;
      int cost = (*it).second;
      if (costuri[nod] + cost < costuri[vecin])
      {
        costuri[vecin] = costuri[nod] + cost;
        q.push(vecin);
      }
    }
  }
}

int main()
{
  ifstream in("dijkstra.in");
  ofstream out("dijkstra.out");

  int n, m, a, b, cost;
  in >> n >> m;

  for (int i = 1; i <= m; i++)
  {
    in >> a >> b >> cost;
    graf[a].push_back(make_pair(b, cost));
  }

  for (int i = 2; i <= n; i++)
  {
    costuri[i] = INT_MAX;
  }

  bfs();

  for (int i = 2; i <= n; i++)
  {
    out << costuri[i] << ' ';
  }

  return 0;
}