#include <bits/stdc++.h>
#define infinity 2000000000
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

struct muchie{
    int dest, cost;
};
muchie var;
vector <muchie> graphs[50002];
bool vizat[50002];
long long distante[50002];
int n, m;

void init_distante()
{
    int i;
    for(i = 2; i <= n; i++)
        distante[i] = infinity;
}

struct something
{
    bool operator() (int x, int y)
    {
        return(distante[x] > distante[y]);
    }
};

priority_queue <int, vector <int>, something> coada;

void dijkstra()
{
    int nod, i, sizer;
    vizat[1] = 1;
    coada.push(1);
    while(!coada.empty())
    {
        nod = coada.top();
        coada.pop();
        sizer = graphs[nod].size();
        for(i = 0; i < sizer; i++)
        {
            if(distante[nod] + graphs[nod][i].cost < distante[graphs[nod][i].dest])
                distante[graphs[nod][i].dest] = distante[nod] + graphs[nod][i].cost;
            if(vizat[graphs[nod][i].dest] == 0)
                coada.push(graphs[nod][i].dest), vizat[graphs[nod][i].dest] = 1;
        }
    }
}

int main()
{
    int i, z, x, y;
    fin >> n >> m;
    for(i = 0; i < m; i++)
    {
        fin >> x >> y >> z;
        var.cost = z;
        var.dest = y;
        graphs[x].push_back(var);
    }
    init_distante();
    dijkstra();
    for(i = 2; i <= n; i++)
    {
        if(distante[i] == infinity)
            fout << 0 << ' ';
        else fout << distante[i] << ' ';
    }
    return 0;
}