#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");

int d[50005];

struct compara
{
    bool operator()(int x, int y)
    {
        return d[x] > d[y];
    }
};
priority_queue<int, vector<int>, compara> coada;

const int oo= (1<<30);

bool viz[50005];

struct ura
{
	int nod,cost;
}a;
vector <ura> v[250005];

int n,m;

void citire()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y,c;
		cin>>x>>y>>c;
		a.nod=y;
		a.cost=c;
		v[x].push_back(a);
	}
}

void dijkstra(int nodS)
{
	for(int i=1;i<=n;i++)
		d[i]=oo;
	d[nodS]=0;

	coada.push(nodS);
	viz[nodS]=true;

	while(!coada.empty())
	{
		int nodC=coada.top();
		coada.pop();
		viz[nodC]=false;
		for(int i=0; i<v[nodC].size();	i++)
		{
			int vec=v[nodC][i].nod;
			int cos=v[nodC][i].cost;
			if(d[nodC]+cos< d[vec])
			{
				d[vec]=d[nodC]+cos;
				if(viz[vec]==false)
				{
					coada.push(vec);
					viz[vec]=true;
				}
			}
		}
	}
}
void afis()
{
    for(int i = 2; i <= n; i++)
    {
        if(d[i] != oo)
            cout << d[i] << " ";
        else
            cout << "0 ";
    }
}

int main()
{
    citire();
    dijkstra(1);
    afis();
    return 0;
}