#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
vector<pair<int,int> > G[50005];
set<pair<int,int> > s;
int n,m,sol[50005];
int main ()
{
f>>n>>m;
for(int i=1;i<=m;i++)
{
    int sursa,dest,cost;
    f>>sursa>>dest>>cost;
    G[sursa].push_back({dest,cost});
}
for(int i=1;i<=n;i++) sol[i]=INF;
sol[1]=0;
s.insert({0,1});
while(!s.empty())
{
    int nodcrt=s.begin()->second;
    int cost=s.begin()->first;
    s.erase(s.begin());
    for(int i=0;i<G[nodcrt].size();i++)
    {
        if(cost+G[nodcrt][i].second<sol[G[nodcrt][i].first])
        {
            s.erase({sol[G[nodcrt][i].first],G[nodcrt][i].first});
            sol[G[nodcrt][i].first]=cost+G[nodcrt][i].second;
            s.insert({cost+G[nodcrt][i].second,G[nodcrt][i].first});
        }
    }


}
for(int i=2;i<=n;i++) {if(sol[i]==INF) g<<0;else g<<sol[i];g<<" ";}
}