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

#define x first
#define y second
#define NMAX 50001

using namespace std;

vector < pair < int , int > > v[NMAX];
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));
    Dist[1] = 0;
    while(! q.empty())
    {
        int nod = q.top().y;
        if(viz[nod] == 0)
        {
            viz[nod] = 1;
            for(int i = 0 ; i < v[nod].size() ; ++ i)
                if(Dist[v[nod][i].x] > Dist[nod] + v[nod][i].y)
                {
                    Dist[v[nod][i].x] = Dist[nod] + v[nod][i].y;
                    q.push(make_pair( - Dist[v[nod][i].x] , v[nod][i].x));
                }
        }
        q.pop();
    }
}

int main()
{
    freopen("dijkstra.in" , "r" , stdin);
    freopen("dijkstra.out" , "w" , stdout);
    scanf("%d %d" , &n , &T);
    for(int i = 1 ; i <= n ; ++ i)
        Dist[i] = 2000000;
    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)
        printf("%d " , Dist[i]);
    return 0;
}