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

using namespace std;

int n, m;
vector<pair<int, int> > vecini[50005];
bool viz[50005];
int sol[50005];

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

    int tmp1, tmp2, tmp3;

    for(int i = 0; i < m; i++){
        scanf("%d %d %d", &tmp1, &tmp2, &tmp3);
        tmp1--;
        tmp2--;
        vecini[tmp1].push_back({tmp2, tmp3});
    }
}

void dijkstra(){
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > Q;
    Q.push({0, 0});

    while(!Q.empty()){
        int x = Q.top().second;
        int y = Q.top().first;

        Q.pop();

        if(viz[x] == true){
            continue;
        }

        viz[x] = true;

        sol[x] = y;

        int l = vecini[x].size();

        for(int i = 0; i < l; i++){
            int z = vecini[x][i].second;
            Q.push({vecini[x][i].second + sol[x], vecini[x][i].first});
        }
    }

    for(int i = 1; i < n; i++){
        printf("%d ", sol[i]);
    }
}

int main()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);

    citire();
    dijkstra();

    return 0;
}