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

using namespace std;

int N, M;

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

int LMIN[50005];
void solve()
{

bool inQ[50005];
    queue<int> Q;

    Q.push(1);

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

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

        Q.pop();
        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;
                }
*/
            }

    }
}

int main()
{

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

    fin>>N>>M;

        int A, B, C;
    for(int i=1;i<=M;++i)
    {
        fin>>A>>B>>C;

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

    solve();

    for(int i=2;i<=N;++i)
        cout<<(LMIN[i] == 99999 ? 0 : LMIN[i])<<" ";

    return 0;
}