#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<<min(a[i]-1,0)<<" ";
    return 0;
}