#include<bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 1e6 + 100;
typedef pair<int,int> pii;

struct node {
    int v;
    int w;
};
vector<node> e[maxn];
int dis[maxn];
bool vis[maxn];
int pre[maxn];

void dijkstra(int s) {
    priority_queue<pii, vector<pii>, greater<pii>> q;
    memset(dis, inf, sizeof(dis));
    dis[s] = 0;
    q.push({dis[s], s});
    while(!q.empty()) {
        pii t = q.top();
        q.pop();
        int u = t.second;
        if(vis[u])
            continue;
        vis[u] = true;
        for(node x:e[u]) {
            int v = x.v;
            int w = x.w;
            if(dis[v]>dis[u]+w) {
                dis[v] = dis[u] + w;
                pre[v] = u;
                q.push({dis[v], v});
            }
        }
    }
}

int main() {
    int n, m, s;
    cin >> n >> m >> s;
    for (int i = 0;i<n;i++) {
        pre[i] = -1;
    }
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].push_back((node){v, w});
        // e[v].push_back((node){u, w});
    }
    dijkstra(s);
    for (int i = 1; i <= n;i++) {
        cout << dis[i] << " ";
    }
    cout << endl;
}

struct Hash() {
    const int mod = 1e9 + 7;
    const int SEED = 13331;
    long long p[maxn], f[maxn], ff[maxn];
    int n;
    void Hash(string s) {
        n = s.size();
        f[0] = s[0] - 'a' + 1;
        p[0] = 1;
        for (int i = 1; i < n; i++) {
            f[i] = (f[i - 1] * SEED % mod + (s[i] - 'a' + 1)) % mod;
            p[i] = p[i - 1] * SEED % mod;
        }
        ff[n - 1] = s[n - 1] - 'a' + 1;
        for (int i = n - 2; i >= 0; i--) {
            ff[i] = (ff[i + 1] * SEED % mod + (s[i] - 'a' + 1)) % mod;
        }
    }
    long long h(int l, int r) {
        if (l == 0)
            return f[r];
        return (f[r] - f[l - 1] * p[r - l + 1] % mod + mod) % mod;
    }
    long long hh(int l, int r)
    {
        if (r == n - 1)
            return ff[l];
        return (ff[l] - ff[r + 1] * p[r - l + 1] % mod + mod) % mod;
    }
};

priority_queue<int,vector<int>,greater<int> >q;//小顶堆
priority_queue<int> q;//大顶堆,默认

struct node{
    int c, fc;
    bool operator < (const node& a) const {
        return fc < a.fc;//大顶
    }
}
priority_queue<node> q;

struct node2{//重写仿函数
    bool oprator() (node a,node b) {
        return a,x<b.x;//大顶
    }
}
priority_queue<node,vector<node>,node2> q;

struct SegTree {
    #define lson l,mid,rt<<1
    #define rson mid+1,r,rt<<1|1
    ll a[maxn << 2];
    int tag[maxn << 2];
    void pushup(int rt) {
        a[rt] = min(a[rt << 1], a[rt << 1 | 1]);
    }
    void push(int rt,int x) {
        a[rt] += x;
        tag[rt] += x;
    }
    void pushdown(int rt) {
        if(!tag[rt])
            return;
        push(rt << 1, tag[rt]);
        push(rt << 1 | 1, tag[rt]);
        tag[rt] = 0;
    }
    void build(int l = 1,int r = n,int rt = 1) {
        if(l==r) {
            a[rt] = 0;
            return;
        }
        int mid = (l + r) >> 1;
        build(lson), build(rson);
        pushup(rt);
    }
    void update(int L, int R, int x, int l = 1, int r = n,int rt = 1) {
        if(L<=l&&r<=R) {
            push(rt, x);
            return;
        }
        int mid = (l + r) >> 1;
        pushdown(rt);
        if(L<=m)
            update(L, R, x, lson);
        if(R>m)
            update(L, R, x, rson);
        pushup(rt);
    }
    ll query(int L, int R, int l = 1, int r = n,int rt = 1) {
        if(L<=l&&r<=R) {
            return a[rt];
        }
        int m = (l + r) >> 1;
        pushdown(rt);
        if(R<=m)
            return query(L, R, lson);
        if(L>m)
            return query(L, R, rson);
        return min(query(L, R, lson), query(L, R, rson));
    }
} f;

#include <bits/stdc++.h>
#include<stdint.h>
#define int long long
#define scan(n) scanf("%lld", &(n))
#define scann(n, m) scanf("%lld%lld", &(n), &(m))
#define scannn(a, b, c) scanf("%lld%lld%lld", &(a), &(b), &(c))
#define prin(n) printf("%lld", (n))
#define pb push_back
#define mp make_pair
#define ms(a) memset(a, 0, sizeof(a))
#define fo(i, a, b) for (int i = (a); i <= (b); i++)
#define ro(i, a, b) for (int i = (a); i >= (b); i--)
const int inf = 0x3f3f3f3f;
using namespace std;
const int maxn = 1e5+100;
int n;
int a[maxn],b[maxn];
int s1[maxn],s2[maxn];
int32_t main() {
    while(scan(n)!=EOF){
        fo(i,1,n)scan(a[i]);
        fo(i,1,n)scan(b[i]);
        int head1=1,head2=1,tail1=1,tail2=1;
        s1[head1]=s2[head2]=inf;
        int maxpos=1;
        fo(i,1,n){
            while(head1<=tail1&&s1[tail1]>a[i])tail1--;
            while(head2<=tail2&&s2[tail2]>b[i])tail2--;
            if(tail1!=tail2)break;
            s1[++tail1]=a[i],s2[++tail2]=b[i];
            maxpos=i;
        }
        cout<<maxpos<<endl;
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 100;
int head[maxn], to[maxn * 2], nxt[maxn * 2], d[maxn * 2], tot;
int n, m;
void add(int x, int y, int w){
    to[++tot] = y; nxt[tot] = head[x]; d[tot] = w; head[x] = tot;
}
int dp[maxn][20], dep[maxn], dis[maxn];
void dfs(int u, int fa){
    dp[u][0] = fa; dep[u] = dep[fa] + 1;
    for (int i = head[u]; i; i = nxt[i]) {
        int v = to[i];
        if (v == fa) continue;
        dis[v] = dis[u] + d[i];
        dfs(v, u);
    }
}
void init(){
    memset(dp, 0, sizeof(dp));
    dep[0] = dis[0] = 0;
    dfs(1, 0); 
    for (int j = 1; j < 20; j++) 
        for (int i = 1; i <= n; i++) 
            dp[i][j] = dp[dp[i][j - 1]][j - 1];
}
int qlca(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);
    int tmp = dep[x] - dep[y];
    for (int i = 0; tmp; i++, tmp >>= 1)
        if (tmp & 1) x = dp[x][i];
    if (x == y) return x;
    for (int i = 19; i >= 0; i--) {
        if (dp[x][i] != dp[y][i]) {
            x = dp[x][i]; y = dp[y][i];
        }
    }
    return dp[x][0];
}
int dist(int x,int y) {
    int u = qlca(x, y);
    int ans =  dis[x] + dis[y] - 2*dis[u];
    return dis[x] + dis[y] - 2*dis[u];
}

#include<bits/stdc++.h>
using namespace std;

bitset<5> b, a;
int main() {
    cout << b << endl; //00000

    b.set(2);
    cout << b << endl;//00100

    a.set(3);
    cout << a << endl;//01000

    b ^= a;//(00100)^(01000)
    cout << b << endl;//01100

    b.reset(3);//00100
    cout << b << endl;

    b.flip();//11011
    cout << b << endl;
}

#include <bits/stdc++.h>
#include<stdint.h>
#define int long long
#define scan(n) scanf("%lld", &(n))
#define scann(n, m) scanf("%lld%lld", &(n), &(m))
#define scannn(a, b, c) scanf("%lld%lld%lld", &(a), &(b), &(c))
#define prin(n) printf("%lld", (n))
#define pb push_back
#define mp make_pair
#define ms(a) memset(a, 0, sizeof(a))
#define fo(i, a, b) for (int i = (a); i <= (b); i++)
#define ro(i, a, b) for (int i = (a); i >= (b); i--)
const int inf = 0x3f3f3f3f;
using namespace std;
const int maxn = 2e5+100;
vector<int>e[maxn];
int siz[maxn];
int ans,n;
int u,v;
void getsize(int v,int u){
    siz[v]=1;
    for(int x:e[v]){
        if(x==u)continue;
        getsize(x,v);
        siz[v]+=siz[x];
    }
}
void dfs(int v,int u,int t){
    ans=max(ans,t);
    cout<<v<<" "<<u<<" "<<t<<endl;
    for(int x:e[v]){
        if(x==u)continue;
        dfs(x,v,t-2*siz[x]+n);
    }
}
int32_t main() {
    scan(n);
    fo(i,1,n-1){
        scann(u,v);
        e[u].pb(v);e[v].pb(u);
    }
    getsize(1,0);
    int t=0;
    fo(i,1,n)t+=siz[i];
    dfs(1,0,t);
    printf("%lld",ans);
    return 0;
}

int c[maxn * 2];
int lowbit(int x) {
    return x & (-x);
}

void add(int i,int d) {
    while(i<maxn*2) {
        c[i] += d;
        i += lowbit(i);
    }
}

int query(int i) {
    int ret = 0;
    while(i>0) {
        ret += c[i];
        i -= lowbit(i);
    }
    return ret;
}

vector<int> prefix_function(int n){
    vector<int> pi(n);
    for (int i = 1; i < n;i++){
        int j = pi[i - 1];
        while(j>0&&t[i]!=t[j])j = pi[j - 1];
        if(t[i]==t[j])j++;
        pi[i] = j;
    }
    return pi;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 6000 + 5;
int fa[maxn],sz[maxn];
struct node{
    int x, y, w;
} e[maxn];
bool operator < (node a,node b) {
    return a.w < b.w;
}
int find(int x) {
    return (x == fa[x] ? x : find(fa[x]));
}
void init(int n) {
    for (int i = 1; i <= n;i++) {
        fa[i] = i;
        sz[i] = 1;
    }
}
int main() {
    int T;
    scanf("%d", &T);
    while(T--) {
        int n;
        scanf("%d", &n);
        init(n);
        for (int i = 1; i <= n-1;i++) {
            scanf("%d%d%d", &e[i].x, &e[i].y, &e[i].w);
        }
        sort(e + 1, e + 1 + n - 1);
        ll ans = 0;
        for (int i = 1; i <= n - 1;i++) {
            int x = find(e[i].x);
            int y = find(e[i].y);
            int w = e[i].w;
            if(x==y)
                continue;
            ans += (w + 1) * (sz[x] * sz[y] - 1);
            fa[x] = y;
            sz[y] += sz[x];
        }
            printf("%lld\n", ans);
    }
}

#include<memory>
int main() {
    std::unique_ptr<int> up,up1;
    up = std::unique_ptr<int>(new int(20));
    up1 = std::unique_ptr<int>(std::move(up));

    std::cout<<*up1<<std::endl; //结果：20
}

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int main(){
	ordered_set<int>  s;
	s.insert(1);
    s.insert(2);
    s.insert(3);
    s.insert(4);
    cout << s.order_of_key(1) << endl; // the number of elements in the s less than 1
    cout << s.order_of_key(2) << endl; // the number of elements in the s less than 2
    cout << s.order_of_key(3) << endl; // the number of elements in the s less than 3
    cout << s.order_of_key(4) << endl; // the number of elements in the s less than 4
	cout << *s.find_by_order(0) << endl; // print the 0-th smallest number in s(0-based)
    auto it = s.find_by_order(1);
    cout << *it << endl;//3
}

//iterative version
for(int mask = 0; mask < (1<<N); ++mask) {
	dp[mask][-1] = A[mask];	
    //handle base case separately (leaf states)
	for(int i = 0;i < N; ++i){
		if(mask & (1<<i))
			dp[mask][i] = dp[mask][i-1] + dp[mask^(1<<i)][i-1];
		else
			dp[mask][i] = dp[mask][i-1];
	}
	F[mask] = dp[mask][N-1];
}

//memory optimized, super easy to code.
for(int i = 0; i<(1<<N); ++i)
	F[i] = A[i];
for(int i = 0;i < N; ++i) {
    for(int mask = 0; mask < (1<<N); ++mask){
        if(mask & (1<<i))
            F[mask] += F[mask^(1<<i)];
    }
}