#include <bits/stdc++.h>

using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
vector<vector<pair<int,int>>> g;
vector<int> nodfrom1;
int n,m;
void dijkstra(int start)
{
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int, int>>> q;
    q.push({0, start});
    nodfrom1[1] = 0;
    while(!q.empty())
    {
        auto u = q.top();
        int ucost = u.first;
        int unod = u.second;

        //cout << u.first <<' ' <<u.second << '\n';
        q.pop();
       /// if(ucost != nodfrom1[unod])
          //  continue;
        for(auto v : g[unod]){

            if(nodfrom1[v.second] >= 0){
                if(nodfrom1[v.second] > v.first + ucost)
                    nodfrom1[v.second] = v.first + ucost, q.push({nodfrom1[v.second], v.second});
            }

            else
            {
                nodfrom1[v.second] = v.first + ucost;
                q.push({nodfrom1[v.second], v.second});
            }

            }
    }
}
int main()
{
    fin >> n>> m;
    nodfrom1.resize(n + 1, -1);
    g.resize(n + 1);
    for(int i = 1; i <= m; i++)
    {
        int u,v,cost;
        fin >> u >> v >> cost;
        g[u].push_back({cost, v});

    }
   // for(int i = 1; i <= n; i++)
      //  for(auto v : g[i])
            //cout << v.second <<' ' << v.first << '\n';
    dijkstra(1);
    for(int i = 2; i <= n; i++)
        fout << (nodfrom1[i] >= 0 ? nodfrom1[i] : 0) <<' ';
    return 0;
}