#include <fstream>
#include <vector>
#include <queue>
#include <functional>
#define NMAX 50010
#define INF 1000000005

using namespace std;

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

struct varf
{
    int x, c;
    friend bool operator > (varf , varf );
};

bool operator > (varf a, varf b)
{
    return a.c > b.c;
}

int n, m, cmin[NMAX], prec[NMAX], start, nr;
bool uz[NMAX];

vector<varf> G[NMAX];
priority_queue<varf, vector<varf>, greater<varf> > H;

void citire();
void dijkstra();
void afisare();

int main()
{
    citire();
    dijkstra();
    afisare();
    return 0;
}

void citire()
{
    int i, a;
    varf aux;
    fin >> n >> m;
    start = 1;
    while (fin >> a >> aux.x >> aux.c)
        G[a].push_back(aux);
    uz[start] = 1;
    for (i = 1; i <= n; i++)
    {
        cmin[i] = INF;
        prec[i] = start;
    }
    cmin[start] = prec[start] = 0;
    for (i = 0; i < G[start].size(); i++)
    {
        H.push(G[start][i]);
        cmin[G[start][i].x] = G[start][i].c;
    }
}
void dijkstra()
{
    int i;
    varf aux, urm;
    nr = 1;
    while (nr < n && !H.empty())
    {
        aux = H.top();
        H.pop();
        if (!uz[aux.x])
        {
            uz[aux.x] = 1;
            nr++;
            for (i = 0; i < G[aux.x].size(); i++)
            {
                if (!uz[G[aux.x][i].x] && cmin[aux.x] + G[aux.x][i].c < cmin[G[aux.x][i].x])
                {
                    cmin[G[aux.x][i].x] = cmin[aux.x] + G[aux.x][i].c;
                    prec[G[aux.x][i].x] = aux.x;
                    urm.x = G[aux.x][i].x;
                    urm.c = cmin[G[aux.x][i].x];
                    H.push(urm);
                }
            }
        }
    }
}
void afisare()
{
    int i;
    for (i = 2; i <= n; i++)
    {
        if (cmin[i] == INF)
            fout << 0 << ' ';
        else
            fout << cmin[i] << ' ';
    }
    fout << '\n';
    fout.close();
}