#include <fstream>
#include <climits>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include<bitset>
#include <map>
#include <cstring>
#include<algorithm>

using namespace std;


int n, m;
int d[50001],vizitat[50001];

struct muchie {
    int vecin;
    int dist;
};

vector<muchie> graf[50001];

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

void resetD()
{
    for (int i = 1; i <= n; i++)
    {
        d[i] = INT_MAX;
    }

}

void algDist() {
    resetD();

    d[1] = 0;
    for(int i=1; i<=n; i++)
    {
        //gasesc nodul cu val min
    int minim=INT_MAX,poz=0;
      for(int j=1; j<=n; j++)
      {
          if(vizitat[j]==0 && d[j]<minim)
          {
              minim=d[j];
              poz=j;
          }
      }
      vizitat[poz]=1;
      for(int j=0; j<graf[poz].size(); j++)
      {
          int cost=graf[poz][j].dist;
          int nod=graf[poz][j].vecin;
          if(d[nod]>d[poz]+cost && vizitat[nod]==0)
          {
              d[nod]=d[poz]+cost;
          }
      }
    }

}



int main()
{
	fin >> n>>m;
	for (int i = 1; i <= m; i++)
	{
        int x, y, cost;
        fin >> x >> y >> cost;
        muchie a;
        a.vecin = y;
        a.dist = cost;
        graf[x].push_back(a);

       // a.vecin = x;
       // graf[y].push_back(a);
	}


    algDist();
    for (int i = 2; i <= n; i++)
    {
        if (d[i] == INT_MAX)
        {
            d[i] = 0;
        }
        fout << d[i] << " ";

    }
	fin.close();
	fout.close();
	return 0;

}