/**
  *  Worg
  */
#include <queue>
#include <cstdio>
#include <vector>

FILE *fin = freopen("dijkstra.in", "r", stdin); FILE *fout = freopen("dijkstra.out", "w", stdout);

const int INF = 1e9 + 5;

struct NodeDist {
  int dist, vertex;

  NodeDist(const int &dist, const int &vertex) {
    this->dist = dist; this->vertex = vertex;
  }

  bool operator <(const NodeDist &other) const {
    return this->dist > other.dist;
  }
};

std::priority_queue<NodeDist > pq;

/*-------- Data --------*/
int n, m;
std::vector<std::vector<NodeDist > > graph;
/*-------- --------*/

void ReadInput() {
  scanf("%d%d", &n, &m); graph.resize(n + 1);

  for(int i = 0; i < m; i++) {
    int u, v, dist; scanf("%d%d%d", &u, &v, &dist);

    graph[u].push_back({dist, v});
  }
}

void RunDijkstra() {
  std::vector<int > dist(n + 1, INF);

  pq.push({0, 1});

  while(!pq.empty()) {
    int vertex = pq.top().vertex, vertexDistance = pq.top().dist;
    pq.pop();

    if(dist[vertex] != INF) continue;

    dist[vertex] = vertexDistance;
    for(auto& itr : graph[vertex]) {
      if(dist[itr.vertex] == INF) {
        pq.push({vertexDistance + itr.dist, itr.vertex});
      }
    }
  }

  for(int i = 2; i <= n; i++) {
    printf("%d ", dist[i] == INF ? 0 : dist[i]);
  }
}

int main() {
  ReadInput();

  RunDijkstra();
  return 0;
}