using namespace std;

#include <set>
#include <map>
#include <list>
#include <deque>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <cctype>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <utility>
#include <iomanip>
#include <fstream>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>

#define oo (1<<30)
#define f first
#define s second
#define II inline
#define db double
#define ll long long
#define pb push_back
#define mp make_pair
#define Size(V) ((ll)(V.size()))
#define all(V) (V).begin() , (V).end()
#define CC(V) memset((V),0,sizeof((V)))
#define CP(A,B) memcpy((A),(B),sizeof((B)))
#define FOR(i,a,b) for(ll (i)=(a);(i)<=(b);++(i))
#define REP(i, N) for (ll (i)=0;(i)<(ll)(N);++(i))
#define FORit(it, x) for (__typeof((x).begin()) it = (x).begin(); it != (x).end(); ++it)
#define printll(x) printf("%lld",(x))
#define printsp() printf(" ")
#define newline() printf("\n")
#define readll(x) scanf("%lld",&(x))
#define debugll(x) fprintf(stderr,"%lld\n",(x))

#define IN "dijkstra.in"
#define OUT "dijkstra.out"

//#define ONLINE_JUDGE

list<struct neighbor>** graph;

list<int>* unvisited;

int nodeCount;
int edgeCount;

int* minDistances;

struct neighbor
{
  int index;
  int distance;
};

void addNeighbor(int A, int B, int d)
{
  struct neighbor neighbor;
  neighbor.index = B;
  neighbor.distance = d;
  graph[A]->push_back(neighbor);
}

void initStructures()
{
  minDistances = new int[nodeCount + 1];
  unvisited = new list<int>();

  graph = new list<struct neighbor>*[nodeCount + 1];

  graph[1] = new list<struct neighbor>();
  minDistances[1] = 0;
 
  for (int i = 2; i <= nodeCount; i++)
  {
    unvisited->push_back(i);
    graph[i] = new list<struct neighbor>();
    minDistances[i] = oo;
  }
}


void readGraph()
{
  int A, B, d;
  for (int i = 0; i < edgeCount; i++)
  {
    cin >> A >> B >> d; 
    addNeighbor(A, B, d); 
    if (A == 1)
    {
      minDistances[B] = d;
    }
  }
}

int getClosest()
{
  int closest = 0;
  int minDist = oo;

  list<int>::iterator it;
  
  for (it = unvisited->begin(); it != unvisited->end(); it++)
  {
    int i = *it;
    if (minDistances[i] < minDist)
    {
      closest = i;
      minDist = minDistances[i];
    }
  }

  if (closest != 0)
  {
    unvisited->remove(closest);
  }

  return closest;
}

void computeShortestPaths()
{
  while (!unvisited->empty())
  {
    int closest = getClosest();  
    if (closest == 0)
    {
      break;
    }
    /* relaxation step */ 
    list<struct neighbor>::iterator it;
    for (it = graph[closest]->begin(); it != graph[closest]->end(); it++)
    {
      struct neighbor n = *it;
      if (minDistances[n.index] > minDistances[closest] + n.distance)
      {
        minDistances[n.index] = minDistances[closest] + n.distance;
      }
    }
  }
}

void outputResult()
{
  for (int i = 2; i <= nodeCount; i++)
  {
    cout << minDistances[i] << " ";
  }
}

void solve(int test) {
  cin >> nodeCount;
  cin >> edgeCount;

  initStructures();

  readGraph();
  computeShortestPaths();

  outputResult();
}

int main() {
#ifndef ONLINE_JUDGE
  freopen(IN,"r",stdin);
  freopen(OUT,"w",stdout);
#endif
    solve(1);
  return 0;
}