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

#define oo 1<<30

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.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];

void solve()
{
    priority_queue <int, vector <int>, greater<int> > 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;
}