#include <iostream>
#include <vector>
#include <utility>
#include <fstream>
#include <queue>
#include <climits>
using namespace std;

int main()
{
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m,i,j,k,l,distanta[50001],vizitat[50001],parinte[50001];
vector<pair <int, int> > v[50001];
queue<int> q;
f>>n>>m;
for(i=1;i<=m;i++)
    {
    f>>j>>k>>l;
    v[j].push_back(make_pair(k,l));
    }
for(i=1;i<=n;i++)
    {
    distanta[i]=INT_MAX;
    vizitat[i]=0;
    parinte[i]=-1;
    }
q.push(1);
vizitat[1]=1;
distanta[1]=0;
while(!q.empty())
    {
    k=q.front();
    q.pop();
    for(i=0;i<v[k].size();i++)
        {
        if(distanta[k]+v[k][i].second<distanta[v[k][i].first])
            {
            distanta[v[k][i].first]=distanta[k]+v[k][i].second;
            parinte[v[k][i].first]=k;
            q.push(v[k][i].first);
            }
        }
    }


for(i=2;i<=n;i++)
    {
    if(distanta[i]==INT_MAX)
        {
        g<<"0 ";
        continue;
        }
    g<<distanta[i]<<" ";
    }
return 0;
}