#include <fstream>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <string.h>
#include <queue>
#include <math.h>
#include <set>
#include <stack>

#define min(a,b) ((a<b)?a:b)
#define max(a,b) ((a<b)?b:a)
#define abs(a) ((a<0)?-a:a)
#define REP(i,a,b) \
	for (int i=a; i<=b; i++)

#define INF 1000000000

using namespace std;

//#define TEST
#ifdef TEST
ifstream fin("input.txt");
ofstream fout("output.txt");
#else
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
#endif // TEST

#define MAXN 2000000001
#define pb push_back
#define mp make_pair
#define MOD 1000000007

typedef long long ll;
typedef pair<int,int> pp;

int n,m;
struct e
{
    int to, w;
};
struct nod
{
    int x,w;
};
vector<e> E[50000];
int state[50000];
int rez[50000];

bool comp(nod a, nod b)
{
	if (a.w==b.w) return (a.x<b.x);
    return (a.w<b.w);
}

multiset<nod,bool (*) (nod,nod)> ss(comp);

void update(int x, int w)
{
    if (w<rez[x])
    {
        nod t;
        t.x=x;
        t.w=rez[x];
        ss.erase(t);
        t.w = w;
        ss.insert(t);
        rez[x] = w;
    }
}


void Dijkstra(int x)
{
    rez[x]=0;
    state[x]=1;
    for (int i=0; i<n; i++)
        if (i!=x) rez[i] = INF;

    for (int i=0; i<n; i++)
    {
        nod a;
        a.x=i;
        a.w=rez[i];
        ss.insert(a);
    }

    while (ss.size())
    {
        nod a;
        a = *ss.begin();
        ss.erase(*ss.begin());
        for (int i=0; i<E[a.x].size(); i++)
            update(E[a.x][i].to,a.w+E[a.x][i].w);
    }
}

int main()
{
    fin>>n>>m;
    for (int i=0; i<m; i++)
    {
        int x,y,z;
        fin>>x>>y>>z;
        e t;
        t.to = y-1;
        t.w=z;
        E[x-1].push_back(t);
    }

    Dijkstra(0);

    for (int i=0; i<n; i++)
        if (rez[i]==INF) rez[i] = 0;

    for (int i=1; i<n; i++)
        fout<<rez[i]<<' ';

	return 0;
}