#include <iostream>
#include <fstream>
#include <algorithm>
#include <limits.h>

using namespace std;

/// pbinfo #1887

ifstream fin("dijkstra2.in");ofstream fout("dijkstra2.out");

int n,m,p;

///n-nr noduri;m-nr muchii;p-sursa

struct muchie
{
    int x,y,d;
};

bool ordine(muchie id1,muchie id2)
{
    if (id1.x!=id2.x)
        return id1.x<id2.x;
    if (id1.y!=id2.y)
        return id1.y<id2.y;
    return id1.d<id2.d;
}

int find_id(int val,int id[],muchie U[],int lo,int hi)
{
    if(lo>hi)
        return -1;
    else
    {
        int mid=(lo+hi)/2;
        if (U[mid].x==val)
        {
            while (U[mid].x==val)
                mid--;
            return mid+1;
        }
        else
        {
            if (U[mid].x>val)
                return find_id(val,id,U,lo,mid-1);
            else
                return find_id(val,id,U,mid+1,hi);
        }
    }
}

void Dijkstra(muchie U[],int id[],int v[])
{
    int f[n+1];
    for (int i=1;i<=n;i++)
        f[i]=0;
    v[0]=INT_MAX;v[p]=0;f[p]=1;
    for (int i=id[p];i<=id[p+1]-1;i++)
        v[U[i].y]=U[i].d;
    for (int k=1;k<=n-1;k++)
    {
        int imin=0;
        for (int i=1;i<=n;i++)
            if (v[i]<v[imin] && f[i]==0)
            imin=i;
        f[imin]=1;
        if (imin!=0)
        {
            for (int i=id[imin];i<=id[imin+1]-1;i++)
            {
                if (f[U[i].y]==0 && v[U[i].y]>v[U[i].x]+U[i].d)
                    v[U[i].y]=v[U[i].x]+U[i].d;
            }
        }
    }
}

int main()
{
    fin>>n>>m;p=1;
    muchie U[m+1];
    for (int i=1;i<=m;i++)
        fin>>U[i].x>>U[i].y>>U[i].d;
    sort(U+1,U+m+1,ordine);
    int id[n+2],v[n+1];
    id[0]=0;id[n+1]=m+1;
    for (int i=1;i<=n;i++)
    {
        v[i]=INT_MAX;
        id[i]=find_id(i,id,U,id[i-1]+1,m+1);
    }
    Dijkstra(U,id,v);
    for (int i=1;i<=n;i++)
    {
        if (v[i]!=INT_MAX)
            cout<<v[i]<<" ";
        else
            cout<<-1<<" ";
    }
    return 0;
}