#include<cstdio>
#include<vector>
#include<queue>
#define NMAX 50001
#define inf 0x3fffff
#define DIM 32768
using namespace std;
char ax[DIM];
int pz,n,m,x,y,z,aux;
struct graf{int nod,cost;}e;
vector<graf> a[NMAX];
vector<int> d(NMAX,inf);
queue<int> Q;
inline void cit(int &x)
{x=0;
 while(ax[pz]<'0'||ax[pz]>'9')
	if(++pz==DIM)fread(ax,1,DIM,stdin),pz=0;
 while(ax[pz]>='0'&&ax[pz]<='9')
	{x=x*10+ax[pz]-'0';
	 if(++pz==DIM)fread(ax,1,DIM,stdin),pz=0;
	}
}
void dijkstra()
{Q.push(1); d[1]=0;
 while(!Q.empty())
	{aux=Q.front(); Q.pop();
	 for(unsigned int i=0;i<a[aux].size();++i)
		{int wnod=a[aux][i].nod,wcost=a[aux][i].cost;
		 if(d[wnod]>d[aux]+wcost) 
			{d[wnod]=d[aux]+wcost;
			 Q.push(wnod);
			}
		}
	}
}
void scrie()
{for(register int i=2;i<=n;++i)
	if(d[i]==inf) printf("0 ");
		else printf("%d ",d[i]);
 printf("\n");
}
int main()
{freopen("dijkstra.in","rt",stdin); freopen("dijkstra.out","wt",stdout);
 
 cit(n);cit(m);
 for(register int i=1;i<=m;++i)
	cit(x),cit(y),cit(z),e.nod=y,e.cost=z,a[x].push_back(e);
 
 dijkstra();
 
 scrie();
 
 return 0;
}