#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <numeric>
#include <cassert>
#define endl '\n'
#define sp ' '
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int maxn = 2005;
char arr[maxn][maxn];
int d[maxn][maxn];
int p[maxn][maxn];
const int inf = 1e9;
int n,m;
void dijkstra(){
using paa = pair<int,pii>;
priority_queue<paa,vector<paa>,greater<paa>> q;
fill(&d[0][0],&d[n-1][m-1] + 1,inf);
d[0][0] = 0;
q.push({0,{0,0}});
while(q.size()){
int curd = q.top().ff;
int curi = q.top().ss.ff;
int curj = q.top().ss.ss;
q.pop();
if(curd != d[curi][curj])
continue;
if(curi<n-1){
if(d[curi+1][curj] > d[curi][curj] + arr[curi][curj]){
d[curi+1][curj] = d[curi][curj] + arr[curi][curj];
q.push({d[curi+1][curj],{curi+1,curj}});
p[curi+1][curj] = 1;
}
}
if(curj<m-1){
if(d[curi][curj+1] > d[curi][curj] + arr[curi][curj]){
d[curi][curj+1] = d[curi][curj] + arr[curi][curj];
q.push({d[curi][curj+1],{curi,curj+1}});
p[curi][curj+1] = -1;
}
}
}
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cerr.tie(nullptr);
cin>>n>>m;
for(int i=0;i<n;i++)
cin >> arr[i];
dijkstra();
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cout << p[i][j] << sp;
}
cout << endl;
}
int i=n-1,j=m-1;
string ans;
ans += arr[i][j];
while(i!=0 || j!=0){
if(p[i][j] == 1){
ans.pb((char)(d[i][j] - d[i-1][j]));
i--;
}
else if(p[i][j] == -1){
ans.pb((char)(d[i][j] - d[i][j-1]));
j--;
}
else
abort();
}
for(int c=(int)ans.size()-1;c>=0;c--){
cout << ans[c];
}
cout << endl;
}
