#include <bits/stdc++.h>

using namespace std;

const int inf = (1<<30);
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int n, m, ans[50001];
bool check[50001];
vector <pair <int, int> > v[50001];
struct compare{

    bool operator()(int x, int y)
    {
        return ans[x] > ans[y];
    }


};
priority_queue <int, vector<int>, compare > q;



int main()
{
    fin >> n >> m;

    for(int i = 1; i <= m; i++)
        {
            int x, y, z;
            fin >> x >> y >> z;
            v[x].push_back(make_pair(y,z));

        }

     for(int i = 2; i <= n; i++)
        ans[i] = inf;
       check[1] = true;
       q.push(1);
     while(!q.empty())
     {
         int k;
         k = q.top();
         q.pop();
         check[k] = false;
         for(int i = 0; i < v[k].size();i++)
         {
             int Vecin, Valoare;
             Vecin = v[k][i].first;
             Valoare = v[k][i].second;
             if(ans[k]+Valoare < ans[Vecin])
             {
                 ans[Vecin] = ans[k]+Valoare;
                 if(check[Vecin] == false)
                    check[Vecin] = true, q.push(Vecin);
             }

         }


     }
     for(int i = 2; i <= n; i++)
        fout << ans[i] << " ";
    return 0;
}