#include <cstdio>
#include <vector>
#include <queue>
#define DMAX 50002
#define INF 1000000000

using namespace std;
FILE * fin=fopen("dijkstra.in", "r");
FILE * fout=fopen("dijkstra.out", "w");

struct vecin{ int vf, c; };

int n, m;
vector<vecin> G[DMAX];
queue<int> Q;
int cmin[DMAX];
bool inQ[DMAX];

void citire();
void init();
void Bellman_Ford();
void afisare();

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

void Bellman_Ford()
{
int val, i;

Q.push(1); inQ[1]=1;
while (!Q.empty())
    {
        val=Q.front();
        Q.pop();
        inQ[val]=0;
        for (i=0; i<G[val].size(); ++i)
            if (cmin[G[val][i].vf]>cmin[val]+G[val][i].c)
                {
                    cmin[G[val][i].vf]=cmin[val]+G[val][i].c;
                    if (!inQ[G[val][i].vf])
                        {
                            inQ[G[val][i].vf]=1;
                            Q.push(G[val][i].vf);
                        }
                }
    }
}

void init()
{
int i;

for (i=1; i<=n; ++i)
    cmin[i]=INF;
cmin[1]=0;
}

void afisare()
{
int i;

for (i=2; i<=n; ++i)
    if (cmin[i]!=INF) fprintf(fout, "%d ", cmin[i]);
        else fprintf(fout, "0 ");
fprintf(fout, "\n");
fclose(fout);
}

void citire()
{
int i, x, y;
vecin v;

fscanf(fin, "%d %d", &n, &m);
init();
for (i=1; i<=m; ++i)
    {
        fscanf(fin, "%d %d %d", &x, &y, &v.c);
        v.vf=y;
        G[x].push_back(v);
    }
}