#include <cstdio>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>

#define NMAX 50005

using namespace std;

int N, M;
vector<pair<int, int> > edges[NMAX];
unsigned int dist[NMAX];

bool comparator(pair<int, int> a, pair<int, int> b)
{
  if(b.second > a.second)
    return false;
  return true;
}

void read()
{
  freopen("dijkstra.in", "r", stdin);
  freopen("dijkstra.out", "w", stdout);
  scanf("%d%d", &N, &M);
  int a, b, c;
  for(int i = 0; i < M; i++)
  {
    pair<int, int> p;
    scanf("%d%d%d", &a, &b, &c);
    p.first = b;
    p.second = c;
    edges[a].push_back(p);
    push_heap(edges[a].begin(), edges[a].end(), comparator);
  }

  for(int i = 2; i <= N; i++)
  {
    dist[i] = -1;
    dist[i] >>= 1;
  }
}

void solve()
{
  queue<int> q;
  q.push(1);
  while(!q.empty())
  {
    int x = q.front();
    q.pop();
    int s = edges[x].size();
    while(s)
    {
      int node = edges[x].front().first;
      unsigned int cost = edges[x].front().second;
      pop_heap(&edges[x][0], &edges[x][s], comparator);
      s--;
      if(dist[x] + cost < dist[node])
      {
        dist[node] = dist[x] + cost;
        q.push(node);
      }
    }
    make_heap(&edges[x][0], &edges[x][s], comparator);
  }
}

int main()
{
  read();
  solve();

  unsigned int u = -1;
  u >>= 1;
  for(int i = 2; i <= N; i++)
    printf("%d ", dist[i] == u ? 0 : dist[i]);
	return 0;
}