#include<cstdio>
#include<queue>
#define oo 0x3f3f3f3f
using namespace std;

struct node
{
    int nd;
    int cost;
    node *next;
};

node *list[50001];
int d[50001], a[50001], n, m;

struct cmp
{
    bool operator()(const int &a, const int &b)const
    {
        if(d[a] > d[b]) return 1;
        return 0;
    }
};

void read()
{
    scanf("%d %d", &n, &m);

    int x, y, z;
    for ( int i = 1; i <= m; ++i )
    {
        scanf("%d %d %d", &x, &y, &z);
        node *q = new node;
        q->nd = y;
        q->cost = z;
        q->next = list[x];
        list[x] = q;
    }
}

void dijkstra()
{
    priority_queue<int, vector<int>, cmp> Q;

    memset(d, oo, sizeof(d));

    d[1] = 0;
    Q.push(1);


    while(!Q.empty())
    {
        int u = Q.top();
        Q.pop();
               node *q = list[u];

                while ( q )
                {
                    if ( d[q->nd] > d[u] + q->cost )
                    {
                        d[q->nd] = d[u] + q->cost;
                        Q.push(q->nd);
                    }
                    q = q->next;
                }

    }

    freopen("dijkstra.out","w",stdout);
    for(int i = 2; i <= n; ++i)
        printf("%d ", d[i] == oo ? 0 : d[i]);

}

int main()
{
    freopen("dijkstra.in","r",stdin);
    read();
    dijkstra();
    return 0;
}