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

using namespace std;

int N, M;

vector<pair<int, int> > V[50005];

int DMIN[50005];

void solve()
{
    queue<int> Q;

    for(int i=1;i<=N;++i)   DMIN[i] = 999999;

    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<=M;++i)
    {
        int A, B, C;
        scanf("%d %d %d", &A, &B, &C);

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

    }

    solve();

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