#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 first;
	int second;
};

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

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

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.first =y;
	  temp.second = 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 . second = 0;
  currentNode . first  = 1;
  Q.push(currentNode);
  viz[start] = true;
  while(!Q.empty()){
    
    currentNode = Q.top();
    Q.pop();
    node nextNode;
      for(unsigned int i = 0 ; i < v[currentNode.first].size();i++){
	   
	  nextNode = v[currentNode.first][i];
	  if(!viz[nextNode.first]){
	  int newCost = nextNode.second + cost[currentNode.first];
	    if(cost[nextNode.first] > newCost){
	      cost[nextNode.first] = newCost;
	      Q.push(nextNode);
	    }
	  }

	}
	viz[start]=true;
    
  }
  
}


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;
}