#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;

int N, M;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

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

int DMIN[5005];

void solve()
{
    bool inQ[5005];
    queue<int> Q;

    memset(DMIN, 0x3f3f3f3f, sizeof(DMIN));
    memset(inQ, false, sizeof(inQ));

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

    while(!Q.empty())
    {
        int now = Q.front();
        Q.pop();
        inQ[now] = false;

        for(vector<pair<int, int> >::iterator it = MAT[now].begin();it != MAT[now].end();++it)
            if(DMIN[now] + it->second < DMIN[it->first])
            {
                DMIN[it->first] = DMIN[now] + it->second;
                if(!inQ[it->first])
                {
                    Q.push(it->first);
                    inQ[it->first] = true;
                }
            }

    }
}

int main()
{

    int i, A, B, C;

    fin>>N>>M;

    for(i=1;i<=M;++i)
    {
        fin>>A>>B>>C;
        MAT[A].push_back(make_pair(B, C));

    }

    solve();

    for(i=2;i<=N;++i)
        fout<<(DMIN[i] < 0x3f3f3f3f ? DMIN[i] : 0)<<" ";

    return 0;
}