#include <stdio.h>
#include <vector>
#include <queue>
#define N 50001
#define inf 100000000
#define pp pair<int,int>
using namespace std;
int n,m,i,x,y,c,d[N];
vector<pp> G[N];
class comp
{
public:
bool operator()(pp a,pp b)
{
return d[a.first]>d[b.first];
}
};
priority_queue<pp, vector<pp>, comp > Q;
void dijkstra()
{
int i,x;
pp p;
for (i=2;i<=n;i++) d[i]=inf;
Q.push(make_pair(1,0));
while (!Q.empty())
{
p=Q.top();
Q.pop();
x=p.first;
if (d[x]!=p.second) continue;
for (i=0;i<G[x].size();i++)
{
y=G[x][i].first;
if (d[y]>d[x]+G[x][i].second)
{
d[y]=d[x]+G[x][i].second;
Q.push(make_pair(y,d[y]));
}
}
}
}
int main()
{
freopen ("dijkstra.in","r",stdin);
freopen ("dijkstra.out","w",stdout);
scanf("%i%i",&n,&m);
for (i = 1; i <= m; i++)
{
scanf("%i%i%i",&x,&y,&c);
G[x].push_back(make_pair(y,c));
}
dijkstra();
for (i=2;i<=n;i++)
printf("%i ",d[i]==inf?0:d[i]);
fclose(stdin);
fclose(stdout);
return 0;
}