#include <bits/stdc++.h>
#define ll long long
using namespace std;
vector<vector<pair<ll,ll>>>g(20);
vector<ll>dis(20,1e18);
void djikstra(ll k){
priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>>pq;
pq.push({0,k});
dis[k] = 0;
while(!pq.empty()){
ll v = pq.top().first;
ll u = pq.top().second;
pq.pop();
if(v > dis[u]){
continue;
}
for(auto it : g[u]){
if(v+it.second < dis[it.first]){
//cout<<u<<" "<<v<<" "<<it.first<<" "<<it.second<<endl;
dis[it.first] = v+it.second;
pq.push({dis[it.first],it.first});
}
}
}
}
int main(){
ll t,a,b,c,d,e,f;
cin>>a>>b;
for(int i = 0;i<b;i++){
cin>>c>>d>>e;
g[c].push_back({d,e});
g[d].push_back({c,e});
}
vector<vector<ll>>dk(a+1,vector<ll>(a+1));
for(int j = 1;j<=a;j++){
for(int k = 1;k<=a;k++){
dis[k] = 1e18;
}
djikstra(j);
for(int k = 1;k<=a;k++){
dk[j][k] = dis[k];
}
}
ll ans = 1e18;
string st;
for(int i = 0;i<(1<<a);i++){
string s;
s = " "+s;
ll c1 = 0;
ll c2 = 0;
for(int j = 0;j<a;j++){
if(1&(i>>j)){
s += 'B';
c1++;
}
else{
s += 'D';
c2++;
}
}
if(c1 == 0 or c2 == 0){
continue;
}
ll mx = 0;
for(int j = 1;j<=a;j++){
ll mn = 1e18;
for(int k = 1;k<=a;k++){
if(s[j] != s[k]){
mn = min(mn,dk[j][k]);
}
}
mx = max(mn,mx);
}
if(ans > mx){
st = s;
ans = mx;
}
}
cout<<ans<<endl;
for(int i = 1;i<=a;i++){
cout<<st[i];
}
}
//By Rashid_Hashimzade
