#include<fstream>
#include<vector>
#include<queue>
#define inf 5000000
#define Mmax 50001
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
struct punct{int x,c;};
vector < punct > a[Mmax];
vector <int> d(Mmax,inf) ;
queue <int> q;
int n,m,x,y,z,nod,cost,aux;
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)//FU(i,i<a[aux].size())
		{cost=a[aux][i].c; nod=a[aux][i].x;
	     if(d[nod]>d[aux]+cost) {d[nod]=d[aux]+cost; q.push(nod);}
		}
	}
}
int main()
{f>>n>>m;
 punct aux1;
 for(register int i=1;i<=m;++i)f>>x>>y>>z, aux1.x=y, aux1.c=z, a[x].push_back(aux1);
 dijkstra();
 for(register int i=1;i<n;++i)if(d[i+1]!=inf) g<<d[i+1]<<" "; else g<<"0 ";
 g<<"\n";
 return 0;
}