#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int n,m;
vector<int> sos[100], cena[100];

int d[100], p[100];

void bfs(int x) {
	for (int i=1;i<=n;i++) d[i]=-1;
    d[x]=0;
    p[x]=-1;
    queue<int> q;
    q.push(x);
    while (!q.empty()) {
    	int x=q.front();
		q.pop();
		for (int y : sos[x]) {
			if (d[y]==-1) {
				d[y] = d[x]+1;
				p[y] = x;
				q.push(y);
			}
		}
    }
    for (int i=1;i<=n;i++) {
    	cout << i << " " << d[i] << " " << p[i] << endl;
    }
}

int v[100];
void dfs(int x) {
	cout << x << endl;
	v[x]=1;
	for (int y : sos[x]) {
		if (v[y]==0) dfs(y);
	}
}

int d2[100];
void dijkstra_n2(int x) {
	int inf=1e9;
	for (int i=1;i<=n;i++) d2[i]=inf;
	for (int i=1;i<=n;i++) d[i]=-1;
	d2[x]=0;
	for (int i=0;i<n;i++) {
		// najblizje vozlisce
		int md=inf, x=-1;
		for (int y=1;y<=n;y++) {
			if (d[y]==-1 && d2[y]<md) {
				md = d2[y];
				x = y;
			}
		}
		// dodaj
		d[x]=d2[x];
		cout << x << " " << d[x] << endl;
		for (int j=0;j<(int)sos[x].size();j++) {
			int z=sos[x][j];
			int c=cena[x][j];
			if (d[x]+c < d2[z]) {
				d2[z]=d[x]+c;
			}
		}
	}
}

typedef pair<int,int> PII;

void dijkstra_mlogn(int x) {
	int inf=1e9;
	for (int i=1;i<=n;i++) d[i]=inf;
	d[x]=0;
	priority_queue<PII, vector<PII>, greater<PII>> pq;
	pq.push({0,x});
	while (!pq.empty()) {
		int dx=pq.top().first, x=pq.top().second;
		pq.pop();
		if (dx!=d[x]) continue;
		cout << x << " " << d[x] << " " << p[x] << endl;
		for (int j=0;j<(int)sos[x].size();j++) {
			int y=sos[x][j];
			int c=cena[x][j];
			if (d[x]+c<d[y]) {
				d[y]=d[x]+c;
				p[y]=x;
				pq.push({d[y],y});
			}
		}
	}
}

int main() {
	//freopen("graf.in","r",stdin);
	cin >> n >> m;
    for (int i=0;i<m;i++) {
    	int a,b,c;
    	cin >> a >> b >> c;
    	sos[a].push_back(b);
    	cena[a].push_back(c);
    	sos[b].push_back(a);
    	cena[b].push_back(c);
    }
    cout << "BFS" << endl;
    bfs(1);
    cout << "DFS" << endl;
    dfs(1);
    cout << "Dijkstra n^2" << endl;
    dijkstra_n2(1);
    cout << "Dijkstra m log n" << endl;
    dijkstra_mlogn(1);
    return 0;
}