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

using namespace std;

int N, M;

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

int LMIN[5005];
void solve()
{

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

    Q.push(1);

    //for(int i=1;i<=5005;++i)
     //   LMIN[i] = 99999, inQ[i] = false;
memset(LMIN, 0xf0f0f, sizeof(LMIN));

memset(inQ, false, sizeof(inQ));

    LMIN[1] = 0;
    inQ[1] = true;
    while(!Q.empty())
    {
        int now = Q.front();
        inQ[now] = false;
        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;

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

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

    solve();

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

    return 0;
}