#include <fstream>
#include <vector>
#include <queue>

using namespace std;
const int NMAX = 50000;
const int INF = 21e8;

ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");

struct muchii {
    int nod, cost;
};
vector <vector <muchii>> v;

struct prio {
    int nod, cost;
    bool operator <(const prio& rhs) const {
        return cost > rhs.cost;
    }
};

int n;
int dist[NMAX + 2];
void dijkstra() {
    for(int i = 1; i <= n; i++)
        dist[i] = INF;
    dist[1] = 0;
    priority_queue <prio> pq;
    pq.push({1, 0});
    while(!pq.empty()) {
        prio now = pq.top();
        pq.pop();
        if(dist[now.nod] < now.cost)
            continue;
        for(auto x : v[now.nod]) {
            if(dist[x.nod] > now.cost + x.cost) {
                dist[x.nod] = now.cost + x.cost;
                pq.push({x.nod, dist[x.nod]});
            }
        }
    }
}

int main()
{
    int m;
    cin >> n >> m;
    v.resize(n + 1);
    for(int i = 1; i <= m; i++) {
        int a, b, cost;
        cin >> a >> b >> cost;
        v[a].push_back({b, cost});
    }
    dijkstra();
    for(int i = 2; i <= n; i++) {
        if(dist[i] == INF)
            dist[i] = 0;
        cout << dist[i] << " ";
    }
    return 0;
}