#include <bits/stdc++.h>

using namespace std;

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

#define pii pair<int, int>
#define pb push_back
#define fi first
#define se second

const int NMAX = 5e4+5;
const int INF = 0x3f3f3f3f;

int n, m, x, y, wt, dist[NMAX];
vector<vector<pii>> graf(NMAX);

void read()
{
    in>>n>>m;
    for (int i=1; i<=m; i++)
        in>>x>>y>>wt, graf[x].pb({y, wt});
}

void Dijkstra(int start)
{
    memset(dist, INF, sizeof dist);

    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, start});

    while (!pq.empty())
    {
        int from, currwt;
        tie(currwt, from) = pq.top();
        pq.pop();

        for (auto to : graf[from])
        {
            if (currwt+to.se < dist[to.fi])
                {
                    dist[to.fi] = currwt+to.se;
                    pq.push({dist[to.fi], to.fi});
                }
        }
    }

}

void solve()
{
    Dijkstra(1);
    for (int i=2; i<=n; i++)
        out<<dist[i]<<' ';
}

int main()
{
    cin.tie(0); cout.tie(0);
    
    read();
    solve();
    return 0;
}