#include<bits/stdc++.h>

#define x first

#define y second

using namespace std;

ifstream in("dijkstra.in");

ofstream out("dijkstra.out");

vector<pair<int,int>> v[50002];

int a[50002];

priority_queue<pair<int,int>> h;

int main()

{

    int n,m,i,nr1,nr2,c;

    in>>n>>m;

    for(i=0;i<m;i++)

    {

        in>>nr1>>nr2>>c;

        v[nr1].push_back({c,nr2});

    }

    h.push({-1,1});

    while(!h.empty())

    {

        while(!h.empty()&&a[h.top().y]>0)

            h.pop();

        if(h.empty())break;

        nr1=h.top().y;nr2=-h.top().x;

        h.pop();

        a[nr1]=nr2;

        for(auto it:v[nr1])

            if(a[it.y]==0||(a[it.y]<0&&-a[it.y]>nr2+it.x))

            {

                a[it.y]=-nr2-it.x;

                h.push({-nr2-it.x,it.y});

            }

    }

    for(i=2;i<=n;i++)

        out<<max(a[i]-1,0)<<" ";

    return 0;

}