#include <cstdio>
#include <vector>
#include <fstream>
#include <queue>
#define MAX_N 50001

using namespace std;

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

struct nod {int n, cost;};

vector <nod> V[MAX_N];
queue <int> Q;
int viz[MAX_N];
int N,M,D[MAX_N];

void citire()
{
    int x,y,z;
    fin>>N>>M;

    for(int i = 1; i <= M; ++i)
    {
        fin>>x>>y>>z;
        nod t;
        t.n = y;
        t.cost = z;
        V[x].push_back(t);
    }
}

void solve()
{
    memset(D, 0x3f3f3f, sizeof D);

    Q.push(1);
    D[1] = 0;
    viz[1] = 1;

    while(!Q.empty())
    {
        int nod = Q.front();
        Q.pop();
        viz[nod] = 0;

        for(typeof V[nod].begin() p = V[nod].begin(); p < V[nod].end(); p++)
            if(D[p->n]>D[nod]+p->cost)
            {
                D[p->n]=D[nod]+p->cost;
                if(viz[p->n]==0)
                {
                    Q.push(p->n);
                    viz[p->n]=1;
                }
            }
    }
}
void afisare()
{

    for(int i = 2; i <= N; ++i)
        fout<<(D[i]>0x3f3f3f?0:D[i])<<" ";
    fout<<"\n";
}

int main()
{
    citire();
    solve();
    afisare();
}