#include <fstream>
#include <queue>

using namespace std;
priority_queue <pair<int, int> > q;
vector <int> v[50005],co[50005];
int best[50005],f[50005];
int main()
{
	ifstream cin("dijkstra.in");
	ofstream cout("dijkstra.out");

    int n,m,c,a,b,h=1;
    pair <int ,int> pa,ca;
    cin>>n>>m;

    for(int i=0;i<m;i++)
	{
		cin>>a>>b>>c;
		v[a].push_back(b);
		co[a].push_back(c);
	}
	for(int i=0;i<50005;i++)
	{
		best[i]=1;
	}

	pa.first=0;
	pa.second=1;
	best[1]=0;
	q.push(pa);
	while(!q.empty())
	{
		pa=q.top();
		q.pop();
		if(f[pa.second]==0)
		{
			for(int i=0;i<v[pa.second].size();i++)
			{
				ca.first=co[pa.second][i]*(-1)+best[pa.second];
				ca.second=v[pa.second][i];
				if(best[ca.second]==1)
				{
					best[ca.second]=ca.first;
					q.push(ca);
				}
				else if(ca.first>best[ca.second])
				{
					best[ca.second]=ca.first;
					q.push(ca);
				}
			}
			f[pa.second]=1;
		}
	}

	for(int i=2;i<=n;i++)
	{
		cout<<best[i]*(-1)<<" ";
	}

    return 0;
}