#include<fstream>
#include<iomanip>
using namespace std;

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

const int INF = 1<<25;
const int N = 1000;
const int M = 1000;
const int START = 1;

struct lista
{
    int poz,val;
    lista *next;
};

int cost[N];
int viz[N];

int n,m;

lista *(dist[N]);

void pushLeft(int a, int b, int x)
{
    lista *p = new lista;

    p->poz = b;
    p->val = x;
    p->next = dist[a];

    dist[a] = p;
}

void afisdist()
{
    lista *p;
    int i;

    for(i=1; i<=n; ++i)
    {
        p = dist[i];
        out<<"nod="<<i<<": ";
        while(p)
        {
            out<<"("<<p->poz<<", "<<p->val<<") ";
            p = p->next;
        }
        out<<"\n";
    }
}

void afismat(int mat[][N], int n, int m)
{
    int i,j;

    for(i=1; i<=n; ++i)
    {
        for(j=1; j<=n; ++j)
            if(j>i)
                if(mat[i][j]!=INF) out<<setw(3)<<mat[i][j];
                else out<<setw(3)<<"@";
            else if(j==i) out<<setw(3)<<"#";
            else out<<setw(3)<<"~";
        out<<"\n";
    }
    out<<"\n";
}

void afisvec(int v[], int n)
{
    int i;

    for(i=1; i<=n; ++i)
        if(v[i]!=INF) out<<setw(3)<<v[i];
        else out<<setw(3)<<"@";
    out<<"\n";
}

void afissol()
{
    int i;
    for(i=2; i<=n; ++i)
        if(cost[i]!=INF) out<<cost[i]<<" ";
        else out<<"0 ";
}

void init()
{
    int i,j;

    for(i=1; i<=n; ++i) cost[i] = INF;

    cost[START] = 0;
    viz[START] = 0;
}

void cit(int &n, int &m)
{
    int i,a,b,x;

    in>>n>>m;

    init();

    for(i=1; i<=m; ++i)
    {
        in>>a>>b>>x;
        pushLeft(a, b, x);
        ///distante[a][b] = x;
    }
}

int nextNod() /// Caut cel mai apropiat nod de subgraful meu
{
    int i,minim,minimPoz;

    minimPoz = INF;
    minim = INF;
    for(i=1; i<=n; ++i)
        if(viz[i]==0 && cost[i]<minim)
        {
            minim = cost[i];
            minimPoz = i;
        }

    return minimPoz;
}

void updateVecini(int nod)  /// Updatez distantele pentru vecinii nodului 'nod' (minime noi)
{
    lista *p;
    int i;

    p = dist[nod];
    while(p)
    {
        i = p->poz;
        cost[i] = min(cost[i], cost[nod] + p->val);

        p = p->next;
    }

    /*for(i=1; i<=n; ++i)
    {
        cost[i] = min(cost[i], cost[nod] + dist[nod][i]);
    }*/
}

void extindArbore()
{
    int poz=0;

    int pas=0;

    poz = nextNod();
    while(poz != INF)
    {
        viz[poz] = 1;
        updateVecini(poz);

        /*out<<"Pas = "<<(++pas)<<"\n";
        out<<"cost: "; afisvec(cost, n);
        out<<"vec:  "; afisvec(viz, n);
        out<<"\n";*/

        poz = nextNod();
    }
}

int main()
{
    int i,a,b;

    cit(n, m);
    //afismat(dist, n, m);
    extindArbore();
    //afisdist();
    afissol();

    return 0;
}