#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ent "\n"

const int maxn = 1e6 + 100;
const ll INF = (ll)1e18 + 100;
const int inf = 1e9 + 100;
const int MOD = 1e9 + 7;
const int maxl = 26;
const int P = 31;

int n, m;
ll d[20][20];
ll mx[maxn];

void test(){
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			d[i][j] = INF;
		}
	}
	for(int i = 1; i <= m; i++){
		int a, b, c;
		cin >> a >> b >> c;
		d[a][b] = min(d[a][b], (ll)c);
		d[b][a] = min(d[b][a], (ll)c);
	}
	for(int k = 1; k <= n; k++){
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++){
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
			}
		}
	}
	int ans = 0;
	for(int mask = 1; mask < (1<<n)-1; mask++){
		vector<int> a, b;
		for(int i = 1; i <= n; i++){
			if(mask & (1<<(i-1))) a.push_back(i);
			else b.push_back(i);
		}
		for(int i: a){
			ll mn = INF;
			for(int j: b){
				mn = min(mn, d[i][j]);
			}
			mx[mask] = max(mx[mask], mn);
		}
		for(int j: b){
			ll mn = INF;
			for(int i: a){
				mn = min(mn, d[i][j]);
			}
			mx[mask] = max(mx[mask], mn);
		}
		if(!ans || mx[ans] > mx[mask]) ans = mask;
	}
	cout << mx[ans] << endl;
	for(int i = 0; i < n; i++){
		if(ans & (1<<i)) cout << 'D';
		else cout << 'B';
	}
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t; t = 1;
    while(t--) test();
    cout << ent;
}