#include <cstdio>
#include <fstream>
#define infi (1<<29)

using namespace std;

struct nod{
    int inf,cost;
    nod *urm;
}*L[10005];

ofstream cout("dijkstra.out");

int C[10005],viz[10005],isin[10005],p,u,costs[10005];
int n,m,curent;

inline void add(const int &a, const int &b, const int &cost){
    nod *p=new nod;
    p->inf=b;
    p->cost=cost;
    p->urm=L[a];
    L[a]=p;
}

void Bell(){
    while(p<=u){
     curent=C[p++];
     viz[curent]++;
     if(viz[curent]>=n)
        cout<<"infinite loop";
    else
          for(nod *vec=L[curent];vec;vec=vec->urm)
                if(costs[vec->inf]>costs[curent]+vec->cost){
                    costs[vec->inf]=costs[curent]+vec->cost;
                    if(!isin[vec->inf]){
                        isin[vec->inf]=1;
                        C[++u]=vec->inf;
                    }
                }
     isin[curent]=0;
    }
}

inline void show(){
    for(int i=2;i<=n;i++){
        if(costs[i]==infi)
         cout<<0<<' ';
        else
         cout<<costs[i]<<' ';
    }
}

int main(){
    FILE* fin=freopen("dijkstra.in","r",stdin);
    int a,b,cost;
    scanf("%d%d",&n,&m);

    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&a,&b,&cost);
        add(a,b,cost);
    }

    for(int i=2;i<=n;i++){
        costs[i]=infi;
    }

    p=u=1;
    C[u]=1;
    Bell();
    show();
}