#include<stdio.h>
#include<vector>
#include<queue>
#include<algorithm>
#define INF 10000000

using namespace std;

vector< pair<int, int> > l[50001];
 queue<int> c;
int n,m,d[50001];
bool inq[50001];
void initial()
{ for(int i=1;i<=n;i++)
	{ d[i]=INF;
      inq[i]=0;
	}
d[1]=0;
}
void relaxare(int u,int p,int w)
{ if(d[p]>d[u]+w)
   { d[p]=d[u]+w;
     if(inq[p]==0)
	       { c.push(p);
	         inq[p]=1;
	       }
   }
}
void rezolvare()
{ initial();
  c.push(1);
  while(!c.empty())
  { int a=c.front();
    c.pop();
	inq[a]=0;
	for(vector<pair<int,int> > ::iterator it=l[a].begin();it!=l[a].end();it++)
	  { int x=it->first;
	    int y=it->second;
		relaxare(a,x,y);
	   
	  }
  }
	
}
int main()
{  freopen("dijkstra.in","r",stdin);
   freopen("dijkstra.out","w",stdout);
   scanf("%d%d",&n,&m);
   for(int i=1;i<=m;i++)
	 { int x,y,z;
		 scanf("%d%d%d",&x,&y,&z);
		l[x].push_back(make_pair(y,z));
	 }
	rezolvare();
for(int i=2;i<=n;i++)
printf("%d ",d[i]);	
	return 0; }