#include <iostream>
#include <vector>
#include <cstdio>
#include <memory.h>
#include <queue>
#define lim 50009

using namespace std;


int n,m;
const int oo = (1<<30)-1;
struct node{

	int index;
	int cost;
};

int viz[lim];
int cost[lim];
vector<node>v[lim];
struct orderByCost{

  bool operator() (node const &a, node const &b) { return a.cost > b.cost; }
};

priority_queue <node, vector<node>, orderByCost>Q;
void read(){

	scanf("%d %d",&n,&m);
	int x,y,c;
	for(int i = 0 ; i < m; i++){
	  scanf("%d %d %d",&x,&y,&c);
	  node temp;
	  temp.index = y;
	  temp.cost  = c;
	  v[x].push_back(temp);
	}
}

void initialize(int start){
  
  for(int i = 1; i <= n; i++)
    cost[i] = oo;  
  
  memset(viz,0,sizeof viz);
  cost[start] = 0;
}

void dijkstra(int start){
  
  initialize(start);
  node currentNode;
  currentNode.cost = 0;
  currentNode.index  = 1;
  Q.push(currentNode);
  viz[start]++;
  while(!Q.empty()){
    currentNode = Q.top();
    Q.pop();
    viz[currentNode.index]++;
    node nextNode;
    for(unsigned int i = 0 ; i < v[currentNode.index].size();i++){
	nextNode = v[currentNode.index][i];
	int newCost = nextNode.cost + cost[currentNode.index];
	  if(cost[nextNode.index] > newCost && !viz[nextNode.index]){
	    cost[nextNode.index] = newCost;
	    Q.push(nextNode);
	  }

    }
  }
  
}


void print(){
    for(int i = 2; i <= n; i++){
      if(cost[i] == oo)
	printf("0 ");
      else
      printf("%d ",cost[i]);
      
    }
    printf("\n");
}
int main(){
      
      freopen("dijkstra.in","r",stdin);
      freopen("dijkstra.out","w",stdout);
      read();
      dijkstra(1);
      print();
      return 0;
}