#include <iostream>
#include <fstream>
#include <queue>
#include <algorithm>

using namespace std;

int N, M, i, j;

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

int LMIN[5005];
bool inQ[5005];
void solve()
{

    queue<int> Q;

    Q.push(1);

    for(i=1;i<=N;++i)
        LMIN[i] = 99999, inQ[i] = false;

    LMIN[1] = 0;
    inQ[1] = true;
    while(!Q.empty())
    {
        int now = Q.front();

        for(vector<pair<int, int> >::iterator it=V[now].begin();it!=V[now].end();++it)
            if(LMIN[now] + it->second < LMIN[it->first])
            {
                LMIN[it->first] = LMIN[now] + it->second;
//Q.push(it->first);

                if(!inQ[it->first])
                {
                    Q.push(it->first);
                    inQ[it->first] = true;
                }

            }

        Q.pop();
    }
}

int main()
{

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

    cin>>N>>M;

    for(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(i=2;i<=N;++i)
        cout<<(LMIN[i] == 99999 ? 0 : LMIN[i])<<" ";

    return 0;
}