#include <iostream>
#include<fstream>
#include<vector>
using namespace std;
int n,m,comp[50005];
vector<int> mat[50005],d[50005];
int t[50005],p[50005];
class heap
{
    public:
    int z[50005];
    int k;
    void insert(int a)
    {
        z[++k]=a;
        int aux,q=k;
        while(t[z[q/2]]>t[z[q]]&&q/2>=1)
        {
            aux=z[q/2];
            z[q/2]=z[q];
            z[q]=aux;
            p[z[q]]=q/2;
            p[z[q/2]]=q;
            q=q/2;
        }
    }
    void remove(int i)
    {
        z[i]=z[n--];
        int q=k,aux;
        while(1)
        {
            q=i;
            if(z[i]>z[i*2]&&i*2<=k)
                q=i*2;
            if(z[q]>z[i*2+1]&&i*2+1<=k)
                q++;
            aux=z[q],z[q]=z[i],z[i]=aux;
            p[z[q]]=i; p[z[i]]=q;
            if(q==i) break;
            i=q;
        }
    }
    void up(int i)
    {
        int aux;
        while(t[z[i/2]]>t[z[i]]&&i/2>=1)
        {
            aux=z[i/2];
            z[i/2]=z[i];
            z[i]=aux;
            p[z[i/2]]=i;
            p[z[i]]=i/2;
            i=i/2;
        }
    }
};heap h;
int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    int i,n1,n2,c,j;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
        t[i]=2000000000;
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&n1,&n2,&c);
        mat[n1].push_back(n2);
        comp[n1]++;
        d[n1].push_back(c);
    }
    t[1]=0;
    p[1]=1;
    h.k=0;
    h.insert(1);
    while(h.k>0)
    {
        i=h.z[1];
        for(j=1;j<=comp[i];j++)
        {
            if(t[j]>t[i]+d[i][j])
                if(t[j]==200000000)
                {
                    t[j]=t[i]+d[j][i];
                    h.insert(j);
                }
                else
                {
                    t[j]=t[i]+d[j][i];
                    h.up(p[j]);
                }
        }
        p[h.z[1]]=-1;
        h.remove(1);
    }

    return 0;
}