#include <cstdio>
#include <vector>
#include <functional>
#include <queue>

using namespace std;

#define inf 9999999
#define dmax 50001
#define pb push_back
#define x first
#define y second

typedef pair<int, int> pi;
vector <pi> v[dmax];
int d[dmax], n, m;
bool use[dmax];
priority_queue <pi> q;

void read()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    int a, b, c;

    scanf("%i %i ",&n, &m);
    for(int i=1; i<=m; i++)
    {
        scanf("%i %i %i", &a, &b, &c);
    v[a].pb(make_pair(c, b));
    }

}

void dijkstra(int x)
{
    for(int i=1; i<=n; i++)
        d[i]=inf;

    //vector <pi> heap;
    //make_heap(heap.begin(), heap.end());

    q.push(make_pair(d[x], x));
    //pun altfel in coada
    //heap.pb(make_pair(d[x], x));
    //push_heap(heap.begin(), heap.end());
    //END

    d[1]=0;

    while(!q.empty())
    {
        pi a=q.top();
        q.pop();
//        pi a=heap.front();
//        pop_heap(heap.begin(), heap.end());
//        heap.pop_back();


       if(a.x<=d[a.y] || a.y==1)
        for(int i=0; i<v[a.y].size(); i++)
        {

            pi h=v[a.y][i];
            if(d[h.y]>h.x+d[a.y])
            {
                d[h.y]=h.x+d[a.y];

                q.push(v[a.y][i]);
//                heap.pb(v[a.y][i]);
//                push_heap(heap.begin(), heap.end());
            }
            }
    }
}

void printd()
{
    for(int i=2;i<=n;i++)
        if(d[i]!=inf)
            printf("%i ", d[i]);
        else printf("0 ");
    printf("\n");
}


int main()
{
    read();

    dijkstra(1);
    printd();
    return 0;
}