#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

#define oo 1<<30

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

int n,m;
vector < vector < pair <int,int> > > List;

void citire()
{
    fin>>n>>m;
    List.reserve(n+1);
    List.resize(n+1);
    int st,dr,cost;
    for (int i=1; i<=m; ++i)
    {
        fin>>st>>dr>>cost;
        List[st].push_back(make_pair(dr,cost));
    }
}

int dest[50005];

struct cmp
{
    bool operator()(const int &left, const int &right) const
    {
        if (dest[left] < dest[right])
            return 0;
        else
            return 1;
    }
};

void solve()
{
    priority_queue <int, vector <int>, cmp > Q;
    for (int i=1; i<=n; ++i)
        dest[i]=oo;
    dest[1]=0;
    Q.push(1);
    while (!Q.empty())
    {
        int x=Q.top();
        Q.pop();
        for (vector< pair < int, int > >::iterator it=List[x].begin(); it < List[x].end(); it++)
            if (dest[it->first] > dest[x] + it->second)
            {
               dest[it->first]=dest[x]+it->second;
               Q.push(it->first);
            }
    }
}

void afis()
{
    for (int i=2; i<=n; ++i)
        if (dest[i]==oo) fout<<"0 ";
        else fout<<dest[i]<<' ';
}

int main()
{
    citire();
    solve();
    afis();
    return 0;
}