#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
#include <cstring>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
const int N=50001,inf=0x3f3f3f3f;
struct nod
{
   int x,cost;
};
vector<nod>H[N];
vector<nod>::iterator it;
int dist[N];
struct comp
{
bool operator() (const nod &A,const nod &B)
{
return A.cost>B.cost;
}
};
priority_queue <nod, vector<nod> , comp> Q;
int main()
{
int n,m,a,i;
nod A,B;
fin>>n>>m;
memset(dist,inf,sizeof(dist));
for(i=1;i<=m;i++)
{
fin>>a>>A.x>>A.cost;
H[a].push_back(A);
}
for(it=H[1].begin();it!=H[1].end();it++)
{
dist[it->x]=it->cost;
Q.push(*it);
}
while(Q.size())
{
A=Q.top();
for(it=H[A.x].begin();it!=H[A.x].end();it++)
{
if(dist[it->x]>dist[A.x]+it->cost)
{
dist[it->x]=dist[A.x]+it->cost;
B.x=it->x;
B.cost=dist[B.x];
Q.push(B);
}
}
Q.pop();
}
for(i=2;i<=n;i++)
{
if(dist[i]==inf) fout<<"0 ";
else fout<<dist[i]<<" ";
}
}