#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>

#define x first
#define y second
#define NMAX 50001
#define INF 0x3f3f3f3f
#define FORIT( it,v ) for( typeof((v).begin()) it=(v).begin(); it!=(v).end(); ++it )

using namespace std;

vector < pair < int , int > > v[NMAX];
vector < pair < int , int > > :: iterator it;
priority_queue < pair < int , int > > q;
int Dist[NMAX] , viz[NMAX];
int n , T , a , b , c;

void dijkstra()
{
    q.push(make_pair(0 , 1));
    while(! q.empty())
    {
        int nod = q.top().y;
        q.pop();
        if(viz[nod] == 0)
        {
            viz[nod] = 1;
            for(it = v[nod].begin() ; it != v[nod].end() ; ++ it)
                if(Dist[it -> x] > Dist[nod] + it -> y)
                {
                    Dist[it -> x] = Dist[nod] + it -> y;
                    q.push(make_pair( - Dist[it -> x] , it -> x));
                }
        }
    }
}

int main()
{
    freopen("dijkstra.in" , "r" , stdin);
    freopen("dijkstra.out" , "w" , stdout);
    scanf("%d %d" , &n , &T);
    for(int i = 2 ; i <= n ; ++ i)
        Dist[i] = INF;
    for( ; T > 0 ; -- T)
    {
        scanf("%d %d %d" , &a , &b , &c);
        v[a].push_back(make_pair(b , c));
    }
    dijkstra();
    for(int i = 2 ; i <= n ; ++ i)
        if(Dist[i] == INF)
            printf("0 ");
        else
            printf("%d " , Dist[i]);
    return 0;
}