#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, M = 5e5 + 5;
int n, m, s, dis[N], book[N];
queue<int>q;

struct node {
	int v, w;
};
vector<node>e[N];

void spfa() {
	for (int i = 1; i <= n; i++) {
		dis[i] = 2147483647;
	}
	dis[s] = 0;
	q.push(s);
	book[s] = 1;
	while (!q.empty()) {
		int tmp = q.front();
		q.pop();
		book[tmp] = 0;
		for (auto [v, w] : e[tmp]) {
			if (dis[v] > dis[tmp] + w) {
				dis[v] = dis[tmp] + w;
				if (!book[v]) {
					book[v] = 1;
					q.push(v);
				}
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		cout << dis[i] << " ";
	}
}

void dijkstra() {
	priority_queue<pair<int, int> >q;
	memset(dis, 0x3f, sizeof(dis));
	dis[s] = 0;
	q.push({0, s});
	while (!q.empty()) {
		int tmp = q.top().second;
		q.pop();
		if (book[tmp])
			continue;
		book[tmp] = 1;
		for (auto [v, w] : e[tmp]) {
			if (dis[v] > dis[tmp] + w) {
				dis[v] = dis[tmp] + w;
				q.push({-dis[v], v});
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		cout << dis[i] << " ";
	}
}

int main() {
	cin >> n >> m >> s;
	for (int i = 1; i <= m; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		e[x].push_back({y, z});
	}
	dijkstra();
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;

struct node {
	int v, w;
};
vector<node>e[N];
int dis[N], book[N], n, m, k, s, t;
int a[N];

void spfa() {
	memset(dis, 0x3f, sizeof(dis));
	dis[1] = 0;
	queue<int>q;
	q.push(1);
	book[1] = 1;
	while (!q.empty()) {
		int tmp = q.front();
		q.pop();
		book[tmp] = 0;
		for (auto [v, w] : e[tmp]) {
			if (dis[v] > dis[tmp] + w) {
				dis[v] = dis[tmp] + w;
				if (!book[v]) {
					book[v] = 1;
					q.push(v);
				}
			}
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	e[1].push_back({1 + n, a[1]});
	for (int i = 1; i <= m; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		e[x].push_back({y, 0});
		e[x].push_back({y + n, a[y]});
		e[x + n].push_back({y + n + n, -a[y]});
		e[x + n].push_back({y + n, 0});
		e[x + n + n].push_back({y + n + n, 0});
		if (z == 2) {
			e[y].push_back({x, 0});
			e[y].push_back({x + n, a[x]});
			e[y + n].push_back({x + n + n, -a[x]});
			e[y + n].push_back({x + n, 0});
			e[y + n + n].push_back({x + n + n, 0});
		}
	}
	spfa();
	if (dis[3 * n] > 0)
		cout << 0 << endl;
	else
		cout << -dis[3 * n] << endl;
	return 0;
}

/*
dis[i]到i点的最小时间
dis[i][j]到i点时间对k取余得数为j的最小时间
dis[v][j] = dis[tmp][(j-w+k)%k]+w

*/
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 5;
struct node {
	int v, w;
};
vector<node>e[N];
int n, m, k, dis[N][101];
int book[N][101];

void bfs() {
	memset(dis, 0x3f, sizeof(dis));
	queue<pair<int, int> >q;
	q.push({1, 0});
	book[1][0] = 1;
	dis[1][0] = 0;
	while (!q.empty()) {
		int tmp = q.front().first;
		int yu = q.front().second;
		q.pop();
		for (int i = 0; i < e[tmp].size(); i++) {
			int v = e[tmp][i].v;
			int w = e[tmp][i].w;
			if (dis[tmp][yu] >= w && dis[v][(yu + 1) % k] > dis[tmp][yu] + 1) {
				dis[v][(yu + 1) % k] = dis[tmp][yu] + 1;
				q.push({v, (yu + 1) % k});
				book[v][(yu + 1) % k] = 1;
			} else if (dis[tmp][yu] < w) {
				int t = w - dis[tmp][yu];
				int Tim = (t + k - 1) / k * k;
				if (dis[tmp][yu] + Tim + 1 > dis[v][(yu + 1) % k])
					continue;
				dis[v][(yu + 1) % k] = dis[tmp][yu] + Tim + 1;
				book[v][(yu + 1) % k] = 1;
				q.push({v, (yu + 1) % k});
			}
		}
	}
}

int main() {
	cin >> n >> m >> k;
	for (int i = 1; i <= m; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		e[x].push_back({y, z});
	}
	bfs();
	if (!book[n][0])
		cout << "-1" << endl;
	else
		cout << dis[n][0] << endl;
	return 0;
}