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

#define pb push_back
using namespace std;

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

const int COST_INF = 1e9 + 5, Nmax = 5e4 + 5;
vector <pair<int,int>> G[Nmax];
priority_queue <pair<int,int>> q;

int main()
{
    int N,M;
    in >> N >> M;
    while(M--)
    {
        int C,X,Y;
        in >> X >> Y >> C;
        G[X].push_back({Y,C});
    }

    q.push({1,0});
    vector <int> dp(N + 1,COST_INF);
    dp[1] = 0;

    while(!q.empty())
    {
        int Nod = q.top().first;
        q.pop();
        for(auto i : G[Nod])
        {
            int cost = i.second;
            if(dp[i.first] > dp[Nod] + cost)
            {
                dp[i.first] = dp[Nod] + cost;
                q.push({i.first,cost});
            }
        }
    }
    for(int i = 2; i <= N; ++i)
    {
        if(dp[i] == COST_INF)
            dp[i] = 0;
        out << dp[i] << " ";
    }
    return 0;
}