#include <iostream>
#include <fstream>
#include <vector>
#define INF 20000001
#define noduri 20001
using namespace std;
int n,m;

vector<int> D,S,T;

struct graf
{
    int nod, cost;
    graf *next;
};

graf *a[noduri];

void add(int where, int what, int cost)
{
    graf *q = new graf;
    q->nod = what;
    q->cost = cost;
    q->next = a[where];
    a[where] = q;
}
void Read()
{
    ifstream f("dijkstra.in");
    f>>n>>m;
    int x,y,cost;
    for(int i=1; i<=m; i++)
    {
        f>>x>>y>>cost;
        add(x,y,cost);
    }
    D.resize(n+1);
    S.resize(n+1);
    T.resize(n+1);
    for(int i=1; i<=n; i++)
        D[i]=-1;
}

int find_k_min()
{
    int k,kmin=0,minim=INF;
    for(k=1; k<=n; k++)
        if(!S[k]&&D[k]<minim)
        {
            minim=D[k];
            kmin=k;
        }
    return kmin;
}
void initialise()
{
    int R=1;
    S[R]=1;
    graf *q=a[R];
    while(q)
    {
        D[q->nod]=q->cost;
        T[q->nod]=R;
        q=q->next;
    }
    for(int x=2; x<=n; x++)
        if(D[x]==-1)
            D[x]=INF;
}

void Dijkstra()
{
    int k;
    k=find_k_min();
    while(k)
    {
        S[k]=1;
        graf *q=a[k];
        while(q)
        {
            if(!S[q->nod]&&D[k]+q->cost<D[q->nod])
            {
                D[q->nod]=D[k]+q->cost;
                T[q->nod]=k;
            }
            q=q->next;
        }
        k=find_k_min();
    }
}
void Write()
{
    ofstream g("dijkstra.out");
    for(int x=2; x<=n; x++)
    {
        if(D[x]==INF)
            g<<0<<" ";
        else g<<D[x]<<" ";
    }

}
int main()
{
    Read();
    initialise();
    Dijkstra();
    Write();

    return 0;
}