#include <stdio.h>
#include <vector>
#include <queue>
#define dim 50001
#define inf 1<<30

using namespace std;

struct muchie
{
    int nod;
    int cost;
};

struct item
{
    int nod;
    int *cost;
};

struct comp
{
    bool operator()(const item &a, const item &b) const
    {
        return *a.cost > *b.cost;
    }
};

priority_queue <item, vector<item>, comp> q;
vector <muchie> a[dim]; //list of neighboors for each node
int n,m,c[dim]; //cost value from node 1 to other nodes

void djk()
{
    int i;
    item i0,i1;
    muchie m0;
    for (i=1;i<n;i++) //all costs are inf at start
        c[i]=inf;
    i1.nod=0; //add fist node
    i1.cost=&c[i1.nod];
    q.push(i1);
    while (!q.empty())
    {
        i0=q.top();
        vector <muchie> ::iterator j;
        for (j = a[i0.nod].begin();j<a[i0.nod].end();j++)
        {
            m0= *j;
            if (c[m0.nod]>(c[i0.nod]+m0.cost)) //i cost of new path is better
            {
                c[m0.nod]=c[i0.nod]+m0.cost;
                i1.nod = m0.nod;
                i1.cost = &c[m0.nod];
                q.push(i1);
            }
        }
        q.pop();
    }
}

int main()
{
    int i,x1,x2,x3;
    muchie x4;
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d %d",&n,&m);
    for (i=0;i<m;i++)
    {
        scanf("%d %d %d",&x1,&x2,&x3);
        x4.nod=x2-1;
        x4.cost=x3;
        a[x1-1].push_back(x4);
    }
    djk();
    for (i=1;i<n;i++)
    {
        if (c[i]<inf)
            printf("%d ",c[i]);
        else
            printf("0 ");
    }
    return 0;
}