#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
pair<int,int>*f[50005];
int k,i,m,x,j,ct[50005],point[50005],i1;
long long g[50005];
const long long inf=1e8;
queue<int>q;
bool h[50005];
int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d%d",&x,&m);
    for(k=1;k<=m;k++)
    {
        scanf("%d%d%d",&i,&j,&i1);
        ct[i]++;
    }
    freopen("dijkstra.in","r",stdin);
    scanf("%d%d",&x,&m);
    for(k=1;k<=x;k++)
        f[k]=new pair<int,int>[ct[k+1]];
    for(k=1;k<=m;k++)
    {
        scanf("%d%d%d",&i,&j,&i1);
        f[i][point[i]].first=j;  f[i][point[i]].second=i1;point[i]++;
    }
    for(k=2;k<=x;k++)
        g[k]=inf;
    for(q.push(1);!q.empty();)
    {
        k=q.front();
        q.pop();
        for(i=0;i<ct[k];i++)
        {
            if(g[k]+f[k][i].second<g[f[k][i].first])
            {
                //
                g[f[k][i].first]=g[k]+f[k][i].second;
                if(!h[f[k][i].first])
                    q.push(f[k][i].first);

            }
        }
    }
    for(k=2;k<=x;k++)
    {
        if(g[k]==inf)
            printf("0 ");
        else
            printf("%lld ",g[k]);
    }


   /* for(k=1;k<=x;k++)
    {
        cout<<k<<": ";
        for(i=0;i<ct[k];i++)
            cout<<f[k][i].first<<" "<<f[k][i].second<<endl;
    }*/
    return 0;
}