12088

#include <bits/stdc++.h>
using namespace std;
struct edge{
	int v,w;
	bool operator<(edge a)const{
		return w>a.w;
	}
};
int n,m,a,b,w,dis[200001],vis[200001],s;
priority_queue <edge> q;
vector<edge> v[200001];
int main(){
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++)cin>>a>>b>>w,v[a].push_back((edge){b,w});
	for(int i=1;i<=200001;i++)dis[i]=2147483647;
	dis[s]=0;
	q.push((edge){s,0});
	while(!q.empty()){
		int f=q.top().v;
		q.pop();
		if(vis[f]) continue;
		for(int i=0;i<v[f].size();i++){
			edge g=v[f][i];
			if(dis[f]+g.w<dis[g.v])dis[g.v]=dis[f]+g.w,q.push((edge){g.v,dis[g.v]});
		}
		vis[f]=true;
	}
	for(int i=1;i<=n;i++)cout<<dis[i]<<' ';
}

#include <iostream>
#include <cmath>
#include <queue>
#include <string.h>
using namespace std;
#define int long long
int n,t;
int a[105][105];
int d[105][105][4];
int xx[4]={-1,0,1,0},yy[4]={0,-1,0,1},cc[4]={0,2,3,1};
struct node{
	int w,x,y,c;
	bool operator<(node a) const{
		return w>a.w;
	}
};
priority_queue<node> q;
void dijkstra(){
	memset(d,127,sizeof(d));
	d[1][1][3]=0;
	q.push((node){d[1][1][3],1,1,3});
	while(!q.empty()){
		int ux=q.top().x,uy=q.top().y,uc=q.top().c;
		q.pop();
		for(int i=0;i<4;i++){
			int nx=ux+xx[i],ny=uy+yy[i],nc=cc[uc];
			if(nx<1||nx>n||ny<1||ny>n) continue;
			int w=0;
			if(nc==3) w=a[nx][ny];
			if(d[ux][uy][uc]+t+w<d[nx][ny][nc]){
				d[nx][ny][nc]=d[ux][uy][uc]+t+w;
				q.push((node){d[nx][ny][nc],nx,ny,nc});
			}
		}
	}
}
signed main(){
	cin>>n>>t;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>a[i][j];
		}
	}
	dijkstra();
	cout<<min(d[n][n][1],min(d[n][n][2],d[n][n][3]));
	return 0;
}