1. #include <iostream>
2. #include <string>
3. #include <algorithm>
4. #include <vector>
5. #include <queue>
6. using namespace std;
7.  
8. vector<pair<int,int> > vec[1000001];
9. int dist[1000001];
10. int prv[1000001];
11.  
12. int main() {
13.     string line;
14.     int y=0;
15.     int n=0;
16.     while (1) {
17.         getline(cin, line);
18.         if (line == "") break;
19.         if (line[line.size()-1] != ' ') line += ' ';
20.         //cout<<"line:"<<line.size()<<endl;
21.         string current = "";
22.         int x = 0;
23.         for (int i=0; i<line.size(); i++) {
24.             char c = line[i];
25.             if (c == ' ') {
26.                 int v = stoi(current);
27.                 int node = 1 + x + y*n;
28.                 //cout<<"x:"<<x<<" y:"<<y<<" node:"<<node<<" v:"<<v<<endl;
29.                 if (x == 0 && y == 0) {
30.                     pair<int,int> p;
31.                     p.first = v;
32.                     p.second = node;
33.                     vec[0].push_back(p);
34.                 }
35.                 if (y > 0) {
36.                     int upper = node - n;
37.                     //cout<<" upper:"<<upper<<endl;;
38.                     pair<int,int> p;
39.                     p.first = v;
40.                     p.second = node;
41.                     vec[upper].push_back(p);
42.                 }
43.                 if (x > 0) {
44.                     int left = node - 1;
45.                     //cout<<" left:"<<left<<endl;
46.                     pair<int,int> p;
47.                     p.first = v;
48.                     p.second = node;
49.                     vec[left].push_back(p);
50.                 }
51.                 current = "";
52.                 x++;
53.             } else {
54.                 current += c;
55.             }
56.         }
57.         //cout<<" po loop x:"<<x<<" y:"<<y<<" n:"<<n<<endl;
58.         n = x;
59.         y++;
60.     }
61.     int m = y;
62.  
63.    priority_queue<pair<int,int>,  std::vector<pair<int,int> >, std::greater<pair<int,int> > > q;
64.    for (int i=0; i<=n*m; i++) {
65.        dist[i] = 1000000001;
66.        pair<int,int> p;
67.        p.first = 0;
68.        p.second = i;
69.        q.push(p);
70.    }
71.    dist[0] = 0;
72.    while(!q.empty()) {
73.        int u = q.top().second;
74.        q.pop();
75.        if (vec[u].size() > 0) {
76.            int v = vec[u][0].second;
77.            int vw = vec[u][0].first;
78.            if (dist[v] > dist[u] + vw) {
79.                 dist[v] = dist[u] + vw;
80.                 pair<int,int> p;
81.                 p.first = dist[v];
82.                 p.second = v;
83.                 q.push(p);
84.             }
85.        }
86.        if (vec[u].size() > 1) {
87.             int v = vec[u][1].second;
88.             int vw = vec[u][0].first;
89.             if (dist[v] > dist[u] + vw) {
90.                 dist[v] = dist[u] + vw;
91.                 pair<int,int> p;
92.                 p.first = dist[v];
93.                 p.second = v;
94.                 q.push(p);
95.             }
96.        }
97.    }
98.    //cout<<"n:"<<n<<" m:"<<m<<endl;
99. //    for (int i=0; i<=m*n; i++) {
100. //        cout<<"i:"<<i<<" dist:"<<dist[i]<<endl;
101. //    }
102.    cout<<dist[m*n]<<endl;
103.  
104.  
105. }