代码：

#include<iostream>
#include<vector>
using namespace std;
#define INF 999999
int main(){
    int n,m,start;
    int from,to,length;
    cin>>n>>m>>start;
    vector<vector<int>> matrix(n + 1,vector<int>(n + 1,INF));
    vector<int> dis(n + 1,INF);//距离
    vector<bool> seek(n + 1,false);//标记
    dis[start] = 0;
    seek[start] = true;
    for(int i = 0;i < m;i++){
        cin>>from>>to>>length;
        matrix[from][to] = length;
    }
    while(true){
        int k = 0;
        for(int j = 1;j <= n;j++){
            if(seek[j] == false && dis[j] < dis[k]){
                k = j;
            }
        }
        if(k == 0) break;
        seek[k] = true;
        //松弛操作
        for(int j = 1;j <= n;j++){
            if(seek[j] == false){
                dis[j] = min(dis[j],dis[k] + matrix[k][j]);
            }
        }
    }
    //输出
    for(int j = 1;j <= n;j++){
        cout<<dis[j]<<" ";
    }
    return 0;
}