#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const int NMAX = 50005;
const int INF =  0x7fffffff;
struct MUCHIE {
  int nod;
  int cost;
  bool operator < (const MUCHIE other) const {
    return this->cost < other.cost;
  }
};
struct NOD {
  int nod;
  int cost;
};
vector <NOD> v[NMAX];
priority_queue <MUCHIE> q;
int cost[NMAX];

int main() {
  int n, m;
  freopen("dijkstra.in", "r", stdin);
  freopen("dijkstra.out", "w", stdout);
  scanf("%d%d", &n, &m);
  for(int i = 1; i <= m; ++i) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    v[a].push_back({b, c});
  }
  for(int i = 2; i <= n; ++i) {
    cost[i] = INF;
  }
  q.push({1, 0});
  while(!q.empty()) {
    MUCHIE nr = q.top();
    q.pop();
    if(nr.cost == cost[nr.nod]) {
      for(auto i : v[nr.nod]) {
        int ncost = nr.cost + i.cost;
        if(cost[i.nod] > ncost) {
          cost[i.nod] = ncost;
          q.push({i.nod, ncost});
        }
      }
    }
  }
  for(int i = 2; i <= n; ++i) {
    printf("%d ", cost[i]);
  }
  printf("\n");
  return 0;
}