#include <stdio.h>
#include <vector>
#include <queue>

#define NMAX 50005
#define MMAX 250005
#define INF 1e9

using namespace std;

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

struct muchie {int x; int y; int cost;} muchii[MMAX];
vector <int> graf[NMAX];
queue <int> q;

int n,m,i,much,x,y,cost,dist[NMAX];
bool used[NMAX];

int main()
{
    fscanf(fin, "%d%d", &n,&m);
    for(i=1; i<=m; ++i)
    {
        fscanf(fin, "%d%d%d", &muchii[i].x,&muchii[i].y,&muchii[i].cost);
        graf[muchii[i].x].push_back(i);
    }

    for(i=1; i<=n; ++i)
    {
        q.push(i);
        dist[i] = INF;
    }

    dist[1] = 0;
    while(!q.empty())
    {
        x = q.front();

        if(used[x])
        {
            q.pop();
            continue;
        }
        else
        {
            for(i=0; i<graf[x].size(); ++i)
            {
                much = graf[x][i];
                y = muchii[much].y;
                cost = muchii[much].cost;

                if(!used[y] and dist[x] + cost < dist[y])
                    dist[y] = dist[x] + cost;
            }

            used[x] = true;
            q.pop();
        }
    }

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

    fclose(fin);
    fclose(fout);
    return 0;
}