#include <bits/stdc++.h>

using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");



vector<int> dijkstra(int src,vector<vector<pair<int, int>>>& g)
{
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    vector<int> dist(g.size(), -1);
    pq.push({src,0});
    dist[src]=0;
    while(!pq.empty())
    {
        auto top=pq.top();
        pq.pop();
        int node=top.first;
        int d=top.second;
        if(dist[node]!=d)continue;
        for(auto vec:g[node])
        {
            if(dist[vec.first]==-1 or dist[vec.first]>d+vec.second)
            {
                dist[vec.first]=d+vec.second;
                pq.push({vec.first,dist[vec.first]});
            }
        }

    }
    return dist;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,m;
    fin>>n>>m;
    vector<vector<pair<int, int>>> g(n+1);

    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        fin>>a>>b>>c;
        g[a].push_back({b,c});
        //v[b].push_back({a,c});
    }

    vector<int>dist = dijkstra(1,g);
    for(int i=2;i<=n;i++)
    {
        if(dist[i]==-1)fout<<'0'<<' ';
        else fout<<dist[i]<<' ';
    }



    return 0;
}