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

using namespace std;

struct muchie
{
    int nod;
    int cost;
};

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

priority_queue <muchie, vector<muchie>, 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;
    muchie n0,n1,n2;
    for (i=1;i<n;i++) //all costs are inf at start
        c[i]=inf;
    n1.nod=0; //add fist node
    n1.cost=0; //cost of path to first node
    q.push(n1);
    while (!q.empty())
    {
        n0=q.top();
        c[n0.nod]=n0.cost; //save the cost
        vector <muchie> ::iterator j;
        for (j = a[n0.nod].begin();j<a[n0.nod].end();j++)
        {
            n1= *j;
            if (c[n1.nod]>(c[n0.nod]+n1.cost)) //i cost of new path is better
            {
                c[n1.nod]=c[n0.nod]+n1.cost;
                n2.nod = n1.nod;
                n2.cost = c[n1.nod];
                q.push(n2);
            }
        }
        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;
}