#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define l long
#define d double
#define in int
#define fo(i, n) for (i = 0; i < n; i++)
#define si(x) scanf('%d', &x)
#define sl(x) scanf('%lld', &x)
#define ss(s) scanf('%s', s) 
#define pi(x) printf('%d', x)
#define pl(x) printf('%lld', x)
#define ps(s) printf('%s', s) 
#define pb push_back 
#define mp make_pair 
#define F first 
#define S second 
#define all(x) x.begin(), x.end() 
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x)) 
typedef pair<int, int> pii; 
typedef pair<ll, ll> pl; 
typedef vector<int> vi; 
typedef vector<ll> vl; 
typedef vector<pii> vpii;
string file = "bellmanford";
const long INF = (1<<31)-1;
ifstream fin(file+".in");
ofstream fout(file+".out");

long N,M;
vector<pair<long,long>>edge[50005];
queue<long>Coada;
void insert_into_graph(l x,l y,l c)
{
    edge[x].push_back(make_pair(y,c));
}
l dmin[50001];
bool negativ;
void BellmanFord()
{
    vector<pair<l,l>> :: iterator it;
    int i,x;
    for(i=1;i<=N;i++)
    {
        dmin[i] = INF;
    }
    int y;
    dmin[1] = 0;
    Coada.push(1);
    while(!Coada.empty())
    {
        x = Coada.front();
        Coada.pop();
        for(it = edge[x].begin(); it != edge[x].end();it++)
        {
            if(dmin[it->first] > dmin[x] + it->second)
            {
                dmin[it->first] = dmin[x] + it->second;
                Coada.push(it->first);     
            }
        }
    }
}

void display()
{
    for(int i=2;i<=N;i++)
    {
        if(dmin[i] != INF)
        {
            fout<<dmin[i]<<" ";
        }
        else fout<<0<<" ";
    }
}

void read()
{
    fin>>N>>M;
    long x,y,c;
    for(int i=1;i<=M;i++)
    {
        fin>>x>>y>>c;
        insert_into_graph(x,y,c);
    }
}

int main() 
{
    read();
    BellmanFord();
    display();
    return 0;
}