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

using namespace std;

int N, M;

vector<vector<pair<int, int> > > V;

void solve(vector<int> &DMIN)
{

    queue<int> Q;

    Q.push(1);
    DMIN[1] = 0;

    while(!Q.empty())
    {
        int cStep = Q.front();
        for(vector<pair<int, int> >::iterator it=V[cStep].begin();it!=V[cStep].end();++it)
        {
            if(DMIN[cStep] + it->second < DMIN[it->first])
            {
                DMIN[it->first] = DMIN[cStep] + it->second;
                Q.push(it->first);
            }
        }
        Q.pop();
    }

}

int main()
{

    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);

    scanf("%d %d", &N, &M);

    for(int i=1;i<=N+1;++i)
        V.push_back(vector<pair<int, int> >());

    for(int i=1;i<=M;++i)
    {
        int A, B, C;
        scanf("%d %d %d", &A, &B, &C);

        V[A].push_back(make_pair(B, C));

    }
/*
for(vector<vector<pair<int, int> > >::iterator it=V.begin();it!=V.end();++it)
    for(vector<pair<int, int> >::iterator it2=(*it).begin();it2!=(*it).end();++it2)
        cout<<it2->first<<" "<<it2->second<<"\n";*/
    vector<int> DMIN(N+1, 999999);

    solve(DMIN);

    for(int i=2;i<=N;++i)
        cout<<(DMIN[i] == 999999 ? 0 : DMIN[i])<<" ";
    cout<<"\n";
    return 0;
}