#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

#define INF 0xf3f3f3f
#define pb push_back
#define mp make_pair
#define Nmax 50100
#define sc second
#define fs first

int cost[Nmax];
char v[Nmax];
vector <pair <int,int> > p[Nmax];
vector <pair <int,int> > :: iterator it;
queue <int> q;
int n,m;

void bellman()
{
    long long cnt;
    int nod;

    memset(cost,INF,sizeof(cost));

    for(cnt=1 , cost[1]=0 , v[1]=1 , q.push(1) ; !q.empty() && cnt<=(long long) n*m; q.pop() ,++cnt)
        {
            nod=q.front();
            v[nod]=0;
            for(it=p[nod].begin() ; it!=p[nod].end();++it)
                {
                    if(cost[nod] + it->sc< cost[it->fs])
                        {
                            cost[it->fs] = cost[nod] + it->sc;
                            if(!v[it->fs])
                                {
                                    q.push(it->fs);
                                    v[it->fs]=1;
                                }
                        }
                }
        }
}

int main()
{
    int i,x,y,c;
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);

    scanf("%d%d",&n,&m);

    for(i=1;i<=m;++i)
        {
            scanf("%d%d%d",&x,&y,&c);
            p[x].pb (mp (y,c));
        }

    bellman();

    freopen("bellmanford.in","r",stdin);

    scanf("%d%d",&n,&m);

    for(i=1;i<=m;++i)
        {
            scanf("%d%d%d",&x,&y,&c);
            if(cost[x]+c<cost[y])
                {
                    printf("Ciclu negativ!");
                    return 0;
                }
        }

    for(i=2;i<=n;++i)
        printf("%d ",cost[i]);

    return 0;
}