#include<fstream>
using namespace std;

#define inf 1<<30
#define nmax 50000

struct nod{int info,cost;
			nod *next;};
nod *graf[nmax];
int a,b,c,n,m,i,k,distanta[nmax],vizitat[nmax],heap[nmax];
void dijkstra();

void swap(int y,int z,int sem) {
  if(sem) {
    vizitat[heap[y]]=z;
    vizitat[heap[z]]=y;
    }
  int t=heap[y];
  heap[y]=heap[z];
  heap[z]=t;
  }
  
int main() {
  ifstream f("dijkstra.in",ifstream::in);
  ofstream g("dijkstra.out",ifstream::out);
  f>>n>>m;
  for (i=0;i<n;i++) {
    f>>a>>b>>c;
	nod *p=new nod;
	p->next=graf[a];
	p->info=b;
	p->cost=c;
	graf[a]=p;
	}
  dijkstra();
  for (i=2;i<=n;i++)
    if (distanta[i]!=inf)
      g<<distanta[i]<<' ';
	else
	  g<<'0 ';
  return 0;
}

void upheap(int x) {
  int tata;
  while (x>1) {
    tata=x/2;
	if (distanta[heap[tata]]>distanta[heap[x]]) {
	  swap(x,tata,1);
	  x=tata;
	  }
	else
	  x=1;
	}
}

void downheap(int x) {
  int fiu;
  while (x<=k) {
    fiu=x;
	if ((x*2)<=k) {
	  fiu=x*2;
	  if (distanta[heap[fiu]]>distanta[heap[fiu+1]] && fiu+1<=k)
	    fiu++;
	  }
	else
	  return;
	if (distanta[heap[x]]>distanta[heap[fiu]]) {
	  swap(x,fiu,1);
	  x=fiu;
	  }
	else
	  return;
	}
}

void dijkstra() {
  for (int j=0;j<n;j++)
    distanta[i]=inf;
  vizitat[++k]=1;
  while (k) {
    int min=heap[1];
    swap(1,k,0);
	vizitat[heap[1]]=1;
	k--;
	downheap(k);
	nod *p=graf[min];
	while (p->next) {
	  if (distanta[p->info]>distanta[min]+p->cost) {
	    distanta[p->info]=distanta[min]+p->cost;
	    if (vizitat[p->info])
		  upheap(vizitat[p->info]);
		else {
		  heap[++k]=p->info;
		  vizitat[p->info]=k;
		  upheap(k);
		  }
		p=p->next;
		}
	  }
	}
}