#include <cstdio>

using namespace std;

#include <vector>
#include <queue>

const int INF = 2000000000;
const int MAXN = 50005;

struct GNode {
  int node, cost;
};

struct QNode {
  int node, cost;
  QNode(int nod, int cos) : node(nod), cost(cos) {}
  bool operator < (const QNode &chestie) const {
    return cost > chestie.cost;
  }
};

priority_queue <QNode> pq;
vector <GNode> v[MAXN];
int dist[MAXN];

int main()
{
    FILE *fin, *fout;
    int n, m, i, x, y, c, nod, cos, d;
    fin = fopen("dijkstra.in", "r");
    fscanf(fin, "%d%d", &n, &m);
    for (i = 2; i <= n; ++i)
      dist[i] = INF;
    for (i = 0; i < m; ++i) {
      fscanf(fin, "%d%d%d", &x, &y, &c);
      v[x].push_back({y, c});
    }
    fclose(fin);
    pq.push({1, 0});
    while (pq.empty() == 0) {
      nod = pq.top().node; cos = pq.top().cost;
      pq.pop();
      if (dist[nod] == cos)
        for (vector <GNode>::iterator it = v[nod].begin(); it != v[nod].end(); ++it) {
          d = dist[nod] + it->cost;
          if (d < dist[it->node]) {
            dist[it->node] = d;
            pq.push({it->node, d});
          }
        }
    }
    fout = fopen("dijkstra.out", "w");
    for (i = 2; i <= n; ++i)
      if(dist[i] == INF)
        fprintf(fout, "0 ");
      else
        fprintf(fout, "%d ", dist[i]);
    fprintf(fout, "\n");
    fclose(fout);
    return 0;
}