#include <bits/stdc++.h>
#define infinit 2147483647


using namespace std;

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

vector<pair<int,int>>muchia[50005];
vector<int> dist,viz;

int n ,m;


int dist_min()
{
    int poz, mini=infinit;

    for(int i=1;i<=n;i++)
    {
        if(viz[i]==0 && dist[i]<=mini)
        {
            mini=dist[i];
            poz=i;
        }
    }
///returneaza pozitia urmatorului celui mai mic cost
    return poz;
}

vector<int> dijkstra(vector<pair<int,int>>muchia[101],int nod)
{int m;

    for(int i = 1; i<=n+1; i++)
    {
        dist.push_back(infinit);
        viz.push_back(0);
    }

    dist[nod] = 0;

    for(int i =1; i<=n; i++)
    {
        m=dist_min();
        ///il marcam ca vizitat ca sa nu plecam iar din el
        viz[m]=1;
        ///daca gasim un drum mai putin costisitor , schimbam dist ul vecinului
        for(int j= 0; j<muchia[m].size(); j++)
        {
            if(viz[muchia[m][j].first]==0 && dist[m]+muchia[m][j].second<dist[muchia[m][j].first])
                dist[muchia[m][j].first]=dist[m]+muchia[m][j].second;
        }
    }

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

}

int main()
{int x,y,c;

fin>>n>>m;

  for(int i=1;i<=m;i++)
    {fin>>x>>y>>c;
    muchia[x].push_back({y,c});

 }

/*for(int i=1;i<=n;i++)
    {
        for(int j=0;j<muchia[i].size();j++)
        cout<<muchia[i][j].first<<" "<<muchia[i][j].second<<", ";
    cout<<endl;}

*/
   vector<int> rezultat=dijkstra(muchia,1);

   /*for (vector<int>::iterator it = rezultat.begin()+2 ; it !=rezultat.end(); ++it)
    cout<<*it<<" ";*/

    return 0;
}