#include <vector>
#include <iostream>
#include <fstream>
#include <string>
#include <cstring>

using namespace std;

int H, W;
vector<int> min_x(30, -1);
vector<int> min_y(30, -1);
vector<int> max_x(30, -1);
vector<int> max_y(30, -1);
vector<bool> exist(30, false);
char grid[33][33]; // processed input.
int g[30][30]; // matrix representation of graph.
vector<int> in_degree(30, 0);
ifstream fin("frameup.in");
ofstream fout("frameup.out");

int ans[30], nans = 0;

void buildGraph() {
    fin >> H >> W;
    for(int i = 0; i < H; ++i) {
        fin >> grid[i];
        for(int j = 0; j < W; ++j) {
            cout << grid[i][j];
            if(grid[i][j] == '.') continue;
            int v = grid[i][j] - 'A';
            if(min_x[v] == -1 || min_x[v]>i) min_x[v] = i;
            if(min_y[v] == -1 || min_y[v]>j) min_y[v] = j;
            if(max_x[v] == -1 || max_x[v]<i) max_x[v] = i;
            if(max_y[v] == -1 || max_y[v]<j) max_y[v] = j;
            exist[v] = true;
        }
        cout << endl;
    }
    
    for(int u = 0; u < 26; ++u) {
        if (!exist[u]) continue;
        for(int y = min_y[u]; y <= max_y[u]; ++y) {
            int v = grid[min_x[u]][y] - 'A';
            if(v != u && !g[u][v]) {
                g[u][v] = 1; ++in_degree[v];
            }
            
            v = grid[max_x[u]][y] - 'A';
            if(v != u && !g[u][v]) {
                g[u][v] = 1; ++in_degree[v];
            }
        }
        
        for(int x = min_x[u]; x <= max_x[u]; ++x) {
            int v = grid[x][min_y[u]] - 'A';
            if(v != u && !g[u][v]) {
                g[u][v] = 1; ++in_degree[v];
            }
            v = grid[x][max_y[u]] - 'A';
            if(v != u && !g[u][v]) {
                g[u][v] = 1; ++in_degree[v];
            }
        }
    }
}

// DFS that generates all topological sorts in alphabetic order.
void dfs() {
    bool all_used = true;
    for(int i = 0; i < 26; ++i) {
        if(exist[i]) {
            all_used = false;
            break;
        }
    }
    
    if(all_used) {
        for(int i = 0; i < nans; ++i) {
            fout << (char)(ans[i] + 'A');
            cout << (char)(ans[i] + 'A');
        }
        fout << endl; cout << endl;
        return;
    }
    
    for(int u = 0; u < 26; ++u) {
        if (!exist[u]) continue;
        if (in_degree[u]) continue;
        exist[u] = false;
        ans[nans++] = u;
        for(int v = 0; v < 26; ++v) {
            if(g[u][v]) --in_degree[v];
        }
        dfs();
        exist[u] = true;
        nans--;
        for(int v = 0; v < 26; ++v) {
            if(g[u][v]) in_degree[v]++;
        }
    }
}

int main() {
    buildGraph();
    dfs();
    return 0;
}

#include <vector>
#include <iostream>
#include <fstream>
#include <climits>
#include <functional>
#include <algorithm>
#include <numeric>

using namespace std;

int N, M, Si, Ei, Ci;
struct Edge {
    int to, cap, rev, index;
    Edge(int to, int cap, int rev, int index) :
    to(to), cap(cap), rev(rev), index(index) {}
};

vector<vector<Edge>> graph;
vector<vector<Edge>> graphCopy;
vector<bool> visited;
vector<Edge*> edges;
void addEdge(int from, int to, int cap, int index) {
    graph[from].emplace_back(Edge(to, cap, (int)graph[to].size(), index));
    graph[to].emplace_back(Edge(from, 0, (int)graph[from].size() - 1, index));
}

// Ford–Fulkerson
int dfs(int v, int t, int f) {
    if (v == t)
    return f;
    visited[v] = true;
    int size = (int)graph[v].size();
    for (int i = 0; i < size; ++i) {
        auto &e = graph[v][i];
        if (visited[e.to] || e.cap <= 0) continue;
        int d = dfs(e.to, t, std::min(f, e.cap));
        if (d <= 0) continue;
        e.cap -= d;
        graph[e.to][e.rev].cap += d;
        return d;
    }
    return 0;
}

int maxFlow(int s, int t) {
    int flow = 0;
    while (true) {
        std::fill(visited.begin(), visited.end(), false);
        int f = dfs(s, t, INT_MAX);
        if (f == 0) return flow;
        flow += f;
    }
}

int main() {
    ifstream fin("milk6.in");
    ofstream fout("milk6.out");
    
    fin >> N /* warehouses - vertices */ >> M /* trucks - edges */;
    graph = vector<vector<Edge>>(N + 1, vector<Edge>());
    
    visited = vector<bool>(N + 1, false);
    for (int i = 0; i < M; ++i) {
        fin >> Si >> Ei >> Ci;
        addEdge(Si, Ei, Ci, i);
        //cout << Si << " " << Ei << " " << Ci << " " << i << endl;
    }
    
    for (int i = 0; i < N; ++i) {
        for (auto &edge : graph[i]) {
            if (edge.cap == 0) continue;
            edges.emplace_back(&edge);
        }
    }

    sort(edges.begin(), edges.end(), [] (Edge *e1, const Edge *e2) {
        return e1->cap > e2->cap;
    });
    
    graphCopy = graph;
    int ans = maxFlow(1, N);
    graph = graphCopy;
    int total = ans;

    vector<int> ret;
    for (int i = 0; i < edges.size(); ++i) {
        //cout << "cap : " << edges[i]->cap << "; index : " << edges[i]->index << endl;
        graphCopy = graph;
        int cap = edges[i]->cap;
        edges[i]->cap -= cap;
        int flow = maxFlow(1, N);
        if (ans - flow == cap) {
            ret.push_back(edges[i]->index);
            graph = graphCopy;
            ans = flow;
        } else {
            graph = graphCopy;
            edges[i]->cap += cap;
        }
    }
    
    fout << total - ans << " " << ret.size() << endl;
    for (auto val : ret) {
        fout << val + 1 << endl;
    }
}