#include <bits/stdc++.h>
#define Nmax 5005
#define INF 2e9+1
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
vector< pair<int,int> >G[Nmax];
set< pair<int,int> > Heap;
int cost[Nmax];
int main()
{int i,j,n,m,k,t,p,r,x,y,z;
f>>n>>m;
for(i=1;i<=m;i++)
{
    f>>x>>y>>z;
    G[x].push_back({y,z});
}
for(i=1;i<=n;i++)
    cost[i]=INF;
cost[1]=0;
Heap.insert({0,1});
int nod,to,dist;
while(!Heap.empty())
{
    nod=Heap.begin()->second;
    Heap.erase(Heap.begin());
    for(vector< pair<int,int> > :: iterator it=G[nod].begin();it!=G[nod].end();it++)
    {
        to=it->first;
        dist=it->second;
        if(cost[to]>cost[nod]+dist)
        {
            if(cost[to]<INF)
                Heap.erase(Heap.find({cost[to],to}));
            cost[to]=cost[nod]+dist;
            Heap.insert({cost[to],to});
        }
    }
}
for(i=2;i<=n;i++)
{
    if(cost[i]==INF) cost[i]=0;
    g<<cost[i]<<' ';
}

    return 0;
}