#include <fstream>
#include <vector>
//#include <set>
using namespace std;

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

const int INF = 99999999;

struct arc{
    int vf;
    int cost;

    /*bool operator < (const arc &src)
    {
        return cost < src.cost;
    }*/
};

vector<arc> v[50010];

int d[50010], n, m;
bool s[50010];

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

    for(int i = 1; i <= m; i++)
    {
        int x, y, c;
        fin >> x >> y >> c;
        arc aux;
        aux.vf = y;
        aux.cost = c;
        v[x].push_back(aux);
    }
    int init = 1;
    for(int i = 0 ; i <= n + 1; i++)
    {
        d[i] = INF;
    }

    int l = v[init].size();

    for(int i = 0 ; i < l; i++)
    {
        d[v[init][i].vf] = v[init][i].cost;
    }
    s[init] = 1;
    d[init] = 0;

    for(int i = 1; i <= n - 1; i++)
    {
        int vf;
        int mn = INF;
        for(int k = 1; k <= n; k++)
        {
            if(s[k] == 0 && d[k] < mn)
            {
                mn = d[k];
                vf = k;
            }
        }
        s[vf] = 1;
        l = v[vf].size();
        for(int j = 0; j < l; j++)
        {
            int vc = v[vf][j].vf;
            int dist = v[vf][j].cost;
            if(d[vf] + dist < d[vc])
            {
                d[vc] = d[vf] + dist;
            }
        }
    }

    for(int i = 2; i <= n; i++)
    {
        fout << d[i] << ' ';
    }

    return 0;
}