#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
int ct[50005],k,i,m,x,j,ct1,point[50005];
pair<int,int>*f[50005];
queue<int>q;
bool g[50005];
const int inf=(1e7)*2;
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,&ct);
        ct[i]++;
    }
    for(k=1;k<=x;k++)
        f[k]=new pair<int,int>[ct[k]+1];
    freopen("dijkstra.in","r",stdin);
    scanf("%d%d",&x,&m);
    for(k=1;k<=m;k++)
    {
        scanf("%d%d%d",&i,&j,&ct1);
        f[i][point[i]].first=j;
        f[i][point[i]].second=ct1;
        point[i]++;
    }
    for(k=1;k<=x;k++)
        point[k]=inf;
    for(q.push(1),g[1]=1,point[1]=0;!q.empty();)
    {
        k=q.front();
        q.pop();
        g[k]=0;
        for(i=0;i<ct[k];i++)
        {
            if(point[f[k][i].first]>point[k]+f[k][i].second)
            {
                point[f[k][i].first]=point[k]+f[k][i].second;
                if(!g[f[k][i].first])
                {
                    q.push(f[k][i].first);
                    g[f[k][i].first]=1;
                }
            }
        }
    }
    for(k=2;k<=x;k++)
    {
        if(point[k]==inf)
            printf("0 ");
        else
            printf("%d ",point[k]);
    }
    printf("\n");
    return 0;
}