#include<fstream>
#include<algorithm>
#include<vector>
#include<queue>
#define inf 0x3f3f3f
using namespace std;
struct nod
{
int y,cost;
};
vector< vector<nod> > mat(50001);
int n,m;
queue<int> q;
vector<int> dist(50001,inf);
int main()
{
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
fin>>n>>m;
for(;m;--m)
{
int x,y,c;
fin>>x>>y>>c;
mat[x].push_back( (nod) {y,c} );
}
q.push(1);
dist[1]=0;
while(!q.empty())
{
int x=q.front();
for(int i=0;i<mat[x].size();++i)
if(mat[x][i].cost+dist[x]<dist[mat[x][i].y])
{
q.push(mat[x][i].y);
dist[mat[x][i].y]=mat[x][i].cost+dist[x];
}
q.pop();
}
for(int i=2;i<=n;++i)
if(dist[i]!=inf)
fout<<dist[i]<<" ";
else
fout<<"0 ";
}