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

using namespace std;

const int NMAX = 50000;

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

int costuri[1 + NMAX];

void bfs()
{
  q.push(make_pair(0, 1));

  while (!q.empty())
  {
    int nod = q.top().second;
    int cost = q.top().first;
    q.pop();

    if (cost >  costuri[nod]) continue; // sare peste for

    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(make_pair(costuri[vecin], 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++)
  {
    if (costuri[i] == INT_MAX)
    {
      costuri[i] = 0;
    }
    out << costuri[i] << ' ';
  }

  return 0;
}