#include <fstream>
#include <climits>
#include <queue>
#include <vector>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int n, m;
vector<pair<int, int>> G[50002];
void citire()
{
    fin>>n>>m;
    for(int i=0; i<m; i++)
    {
        int x, y, c;
        fin>>x>>y>>c;
        G[x].push_back({y, c});
    }
}
auto cmp=[](pair<int, int> a, pair<int, int> b)
{
    if(a.second>b.second)
        return true;
    return false;
};
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> q(cmp);
int dmin[50001];
vector<bool>viz(50001, false);
void dijkstra()
{
    for(int i=2; i<=n; i++)
        dmin[i]=INT_MAX;
    q.push({1, 0});
    while(!q.empty())
    {
        int x=q.top().first;
        q.pop();
        if(viz[x])
            continue;
        viz[x]=true;
        for(auto i: G[x])
            if(dmin[i.first]>dmin[x]+i.second)
                dmin[i.first]=dmin[x]+i.second, q.push({i.first, dmin[i.first]});

    }
}
int main()
{
    citire();
    dijkstra();
    for(int i=2; i<=n; i++)
        if(dmin[i]==INT_MAX)
            fout<<0<<" ";
        else fout<<dmin[i]<<" ";
    return 0;
}