#include <stdio.h>
#include <set>
#include <vector>
#include <utility>
#include <iterator>

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

using namespace std;

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

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

struct muchie {int x; int y; int cost;} muchii[MMAX];
vector <int> graf[NMAX];
set < pair <int,int> > neviz;
set < pair <int,int> > ::iterator itr;
pair <int,int> actual;

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);
    }

    neviz.insert(make_pair(0,1)); //cost 0, nod 1
    for(i=2; i<=n; ++i)
    {
        dist[i] = INF;
        neviz.insert(make_pair(dist[i], i));
    }

    while(!neviz.empty())
    {
        itr = neviz.begin();
        actual = *itr;
        neviz.erase(itr);
        used[actual.second] = true;

        for(i=0; i<graf[actual.second].size(); ++i)
        {
            much = graf[actual.second][i];
            y = muchii[much].y;
            cost = muchii[much].cost;

            if(!used[y] and actual.first+cost < dist[y])
            {
                dist[y] = actual.first + cost;
                used[y] = true;
                neviz.insert(make_pair(dist[y], y));
            }
        }
    }

    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;
}