#include <bits/stdc++.h>
#define vecin vec.first
#define distanta vec.second

using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

const int N = 50010;
const int oo=1000000010;
vector<pair<int,int>> v[N];
int n,m,x,y,c,d[N];
queue<int> q;
bitset<N> in_coada;
int main()
{
    f>>n>>m;
    for(; m; m--)
    {
        f>>x>>y>>c;
        v[x].push_back(make_pair(y,c));
    }
    for(int i=2; i<=n; i++)
        d[i]=oo;
    q.push(1);
    in_coada[1]=1;
    while(q.size())
    {
        x=q.front();
        q.pop();
        in_coada[x]=0;
        for(auto vec:v[x])
                if(d[x]+distanta<d[vecin])
                {
                    d[vecin]=d[x]+distanta;
                    if(!in_coada[vecin])q.push(vecin);
                }
    }
    for(int i=2;i<=n;i++)
    {
        if(d[i]==oo)
            d[i]=0;
        g<<d[i]<<' ';
    }
    return 0;
}