Texniti_Noimosini_Seira_1

/// Konstantinos Tziapouras
/// Texniti Noimosini (Seira Askiseon 1)

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

int n,m;
vector < pair < int,int > > row;
vector < vector < pair < int,int > > > a(20,row);

vector < pair<int,string> > ans;
string mapping[12] = {"","s","b","c","d","a","e","k","h","i","j","g"};
int v[20]={};

void dfs(int start,string path,int dist){

    if(start == 11){

        ans.push_back(make_pair(dist,path));
        return;
    }

    v[start]=1;

    for(int i=0;i<a[start].size();i++){
        if(v[a[start][i].first]==0){
            string new_path = path + mapping[a[start][i].first];
            int new_dist = dist + a[start][i].second;
            dfs(a[start][i].first , new_path , new_dist);
        }
    }

    v[start]=0;

}

int main(){

cin>>n>>m;

for(int i=0;i<m;i++){
    int o,oo,ooo;
    cin>>o>>oo>>ooo;
    a[o].push_back(make_pair(oo,ooo));
}

dfs(1,"s",0);

cout<<"Solutions "<<ans.size()<<endl;
sort(ans.begin(),ans.end());
for(int i=0;i<ans.size();i++){
    cout<<ans[i].first<< " "<<ans[i].second<<endl;
}

}


/*
Input
-------
11 20
1 2 2
1 3 1
1 5 1
2 3 2
2 7 1
2 6 3
3 4 1
3 7 1
3 9 3
5 4 2
5 9 6
4 9 3
6 11 6
7 8 1
7 10 7
7 11 9
8 9 3
8 10 7
9 10 3
10 11 3

Output
--------
Solutions 19
10 scijg
11 sbeg
11 scdijg
11 sckg
12 sadijg
12 sbkg
12 sckhijg
12 sckjg
13 saijg
13 sbcijg
13 sbkhijg
13 sbkjg
13 sckhjg
14 sbcdijg
14 sbckg
14 sbkhjg
15 sbckhijg
15 sbckjg
16 sbckhjg

*/