#include<fstream>
#include<vector>
using namespace std;
int n,m;
bool v[50010];
int sol[50010];
vector <short> cost[50010],vecin[50010];
void citire()
{int i,y,x,c;
ifstream in("dijkstra.in");
in>>n>>m;
for(i=0;i<m;i++)
	{in>>x>>y>>c;
	vecin[x].push_back(y);
	cost[x].push_back(c);
	}
in.close();
}
void dijkstra()
{int i,mn,j,nod;
for(i=2;i<=n;sol[i]=51123456,i++);
for(i=0;i<=n;i++)
	{mn=51123455;
	for(j=1;j<n;j++)
		if(!v[j]&&mn>sol[j])
			{nod=j;
			mn=sol[j];
			}
	v[nod]=1;
	for(j=0;j<vecin[nod].size();j++)
		if(!v[vecin[nod][j]]&&sol[vecin[nod][j]]>sol[nod]+cost[nod][j])
			sol[vecin[nod][j]]=sol[nod]+cost[nod][j];
	}
}
int main()
{
citire();
dijkstra();
ofstream out("dijkstra.out");
for(int i=2;i<=n;i++)
	out<<sol[i]<<" ";
out<<'\n';
out.close();
return 0;
}