#include <fstream>
#include <vector>
#include <set>
#include <utility>
#define INF 2000000000
#define DIM 50010

using namespace std;

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

set <pair <int, int> > s;
vector <pair<int, int > > L[DIM * 5];
int n, m, x, y, cost, nr;
int D[DIM * 2], v[DIM * 2];
pair <int, int> p;

int main()
{
    fin >> n >> m;

    for(int i = 1; i <= m; i ++)
    {
        fin >> x >> y >> cost;
        L[x].push_back(make_pair(y, cost));
    }

    for(int i = 1; i<= n; i ++)
    {
        D[i] = INF;
    }

    D[1] = 0;
    s.insert(make_pair(0 , 1));

    while(nr <= n)
    {
        if(s.empty())
        {
            break;
        }
        p = *s.begin();
        s.erase(s.begin());
        nr ++;
        v[p.second] = 1;

        for(vector <pair< int, int> >::iterator it = L[p.second].begin(); it != L[p.second].end(); it ++)
        {
            if(D[ it -> first ] > D[p.second]  + it -> second)
            {
                s.erase(make_pair(D[it -> first],it -> first));
                D[ it -> first ] = D[p.second]  + it -> second;
                s.insert(make_pair(D[it -> first],it -> first));
            }
        }

    }
    for(int i = 2; i <= n; i ++)
    {
        if(D[i] != INF)
        {
            fout << D[i] << " ";
        }
        else
        {
            fout << "0" << " ";
        }
    }
    return 0;
}