#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;
};
struct cmp{
    bool operator() (const muchie &a, const muchie &b) const
  {
      return a.dist>b.dist;
  }
};

priority_queue < muchie, vector <muchie>, cmp> heap;

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();
    while(!heap.empty())
    {
        int nod=heap.top().vecin;
        int cost=heap.top().dist;
        heap.pop();
        if(vizitat[nod]==1)
        {
            continue;
        }
        vizitat[nod]=1;
        for(int i=0; i<graf[nod].size(); i++)
        {
            int vecin=graf[nod][i].vecin;
            int dist=graf[nod][i].dist;
            if(vizitat[vecin]==0 && d[vecin]>cost+dist)
            {
                d[vecin]=cost+dist;
                heap.push({vecin,d[vecin]});

            }
        }
    }
}



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;

}