#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
#include <string>

using namespace std;

const int N = 510;
int n,m,c1,c2;
//邻接矩阵
int g[N][N];
int dist[N];
bool s[N];
int teams[N];
//path 记录前驱节点这样只能记录一个
int path[N];
vector<int> p[N];
//
bool visited[N];

int dijkstra(){
    memset(dist,0x3f,sizeof(dist));
    dist[0] = 0;
    for(int i=0; i<n; i++){
        int mindist = -1;
        for(int j=0; j<n; j++){
            if(s[j] == false && (mindist == -1 ||dist[j] < mindist) )
                mindist = j;       
        }   
        s[mindist] = true;
        for(int j=0; j<n; j++){   
            if(mindist != j &&dist[j] == dist[mindist] + g[mindist][j]){
                //这里必须先判断要不第二个条件也恒成立
                p[j].push_back(mindist);
            }
            if(dist[j] > dist[mindist] + g[mindist][j]){
                p[j].clear();
                p[j].push_back(mindist);
                dist[j] = dist[mindist] + g[mindist][j];
            }
        }
    }

}
//获取0-x最短路径条数
int get_path_num(int x){
    //return 1;
    if(x == 0) return 1;
    int res =0;
    for(auto i = p[x].begin(); i!=p[x].end(); i++)
        res += get_path_num(*i);
    return res;
}
//输出所有0-x最短路径
    //1.入栈再出栈(单条最短路径)
    //2.递归（多条最短路径）
vector<string> v;
string cur = "";
void print_path(int x,string cu){
    cu += x + '0';
    if(x == 0){
        reverse(cu.begin(),cu.end());
        cout <<cu <<endl;
        v.push_back(cu);
        return;
    }
    for(auto i = p[x].begin(); i!=p[x].end(); i++){
        print_path(*i,cu);
    }   
}
void dfs(int x){
    visited[x] = true;
    for(int i=0; i<n; i++){
        if(x!=i && g[x][i]!= 0x3f3f3f3f && !visited[i])
            dfs(i);
    }
}

int main(){
    cin >>n >>m >>c1 >>c2;

    for(int i=0; i<n; i++)
        cin >>teams[i];

    for(int i=0; i<n; i++)
        for(int j=0; j<N; j++)
            if(i == j) g[i][j] = 0;
            else g[i][j] = 0x3f3f3f3f;
    for(int i=0; i<m; i++){   
        int x,y,d;
        cin >>x >>y >>d;
        g[x][y] = g[y][x] = d; 
    }

    dijkstra();
    dfs(0);
    print_path(2,cur);

}