#include <iostream>
#include<fstream>
#include<vector>
#include<queue>
#define inf 696969
#define NMAX 50001
using namespace std;

int viz[50001],prec[50001],d[50001];

typedef struct{
    int v;
    int value;
}node;

bool operator<(node a, node b)
{
    return (a.value > b.value);
}

vector<node> cost[50001];
priority_queue<node> q;

void drum(int x, int vf)
{
    if(vf!=x)
        drum(x,prec[vf]);
    cout<<vf<<" ";
}

void dijkstra(int x0, int n)
{
    int i,j;
    viz[x0]=1;
    for(i=0;i<cost[x0].size();i++)
    {
        d[cost[x0][i].v] = cost[x0][i].value;
       // cout<<cost[x0][i].v<<" ";
        prec[cost[x0][i].v] = x0;
        q.push(cost[x0][i]);
    }

    for(i=1;i<=n;i++)
    {
        if(d[i]==0)
        {
            d[i]=inf;
            node nod;
            nod.v = i;
            nod.value=inf;
            //q.push(nod);
        }
    }

    while(!q.empty())
    {
        node nod = q.top();
        q.pop();

        if(viz[nod.v]==1)
            continue;

        viz[nod.v]=1;
        int u = nod.v;
        for(i=0;i<cost[u].size();i++)
        {
            if(viz[cost[u][i].v]==0 &&
               d[cost[u][i].v] > d[u] + cost[u][i].value)
            {
                d[cost[u][i].v] = d[u] + cost[u][i].value;
                prec[cost[u][i].v] = u;
                node newnod;
                newnod.v = u;
                newnod.value = d[cost[u][i].v];
                q.push(newnod);
            }
        }
    }
}

int main()
{
    int m,n,i,j,x,y;
    fstream f, out;
    f.open("dijkstra.in",ios::in);
    out.open("dijkstra.out",ios::out);
    f>>n>>m;

    for(i=1;i<=m;i++)
    {
        f>>x>>y;
        int val;
        f>>val;
        node nod;
        nod.v = y;
        nod.value=val;
        cost[x].push_back(nod);
    }

    /*for(i=1;i<=n;i++)
    {
        cout<<i<<": ";
        for(j=0;j<cost[i].size();j++)
            cout<<"("<<cost[i][j].v<<" "<<cost[i][j].value<<") ";
        cout<<endl;
    }*/
    dijkstra(1,n);

    for(i=2;i<=n;i++)
        if(d[i]<inf)
        {
            //cout<<"\nDe la "<<x0<<" la "<<i<<" costul minim este: "<<d[i]<<" si varfurile: ";
            out<<d[i]<<" ";
            //drum(x0,i);
        }
        else
            out<<"0 ";

}