#include <fstream>
#include <iostream>
#include <cstdio>
#include <bitset>
#include <vector>

const long infinit=2000000000;

using namespace std;

int main()
{
	
	int n,m,x,y,z,i;
	ifstream f("dijkstra.in");
	f>>n>>m;
	vector <int> drum;         // }
 	vector <short> selected; //  }
	vector <int> parinte;    //   }
	vector <vector<int> > a;
	drum.reserve(n);
	selected.reserve(n);
	parinte.reserve(n);
	a.reserve(n);
	for (i=0; i<n; i++)
		a[i].reserve(n);
	/*for (i=0; i<m; i++) {
		f>>x>>y>>z;
		a[x][y]=z;
		a[y][x]=z;
	}
	f.close();
	for (i=1; i<=n; i++) {
		drum[i]=infinit;
		parinte[i]=1;
		selected[i]=0;
	}
	drum[1]=0;
	int dmin,nmin;
	while (true) {
		dmin=infinit;
		for (i=1; i<=n; i++)
			if (drum[i]<dmin && selected[i]==0) {
				dmin=drum[i];
				nmin=i;
			}
		if (dmin==infinit) break;
		selected[nmin]=1;
		for (i=1; i<=n; i++)
			if (a[nmin][i]!=0 && selected[i]==0 && dmin+a[nmin][i]<drum[i]) {
				drum[i]=dmin+a[nmin][i];
				parinte[i]=nmin;
			}
	}
	freopen("dijkstra.out","w",stdout);
	for (i=2; i<=n; i++) 
		if (drum[i]==infinit) printf("%d ",0);
		else printf("%d ",drum[i]);*/
	return 0;
}