#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 + 30;
const int INF = 0x3f3f3f3f;

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

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

void dijkstra(int start)
{
    memset(dist, INF, sizeof dist);
    set<pii> edges;
    edges.insert({0, start});

    while (!edges.empty())
    {
        int from, currwt;
        tie(currwt, from) = *(edges.begin());
        edges.erase(edges.begin());

        for (auto to : graf[from])
            if (currwt + to.se < dist[to.fi])
            {
                if (dist[to.fi]!=INF) //exista o distanta deja calculata, o stergem
                    edges.erase({dist[to.fi], to.fi});

                dist[to.fi] = currwt+to.se;
                edges.insert({dist[to.fi], to.fi});
            }
    }


}

void solve()
{
    dijkstra(1);
    for (int i=2; i<=n; i++)
        dist[i] == INF ? out<<0<<' ' : out<<dist[i]<<' ';   
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(false);

    read();
    solve();

    return 0;
}