#include <fstream>
#include <vector>
#include <set>
#include <algorithm>
#define INF 2000000001
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
vector <int> muc[50011],cost[50011];
set <pair<int,int> > s;
int n,m,k,x,y,z,i,d[50011],p;
int main()
{
    f>>n>>m;
    k=1;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>z;
        muc[x].push_back(y);
        cost[x].push_back(z);
    }
    for(i=1;i<=n;i++)
    {
        d[i]=INF;
        s.insert(make_pair(INF,i));
    }
    s.erase(s.find(make_pair(INF,k)));
    d[k]=0;
    for(i=0;i<muc[k].size();i++)
    {
        s.erase(s.find(make_pair(INF,muc[k][i])));
        d[muc[k][i]]=cost[k][i];
        s.insert(make_pair(d[muc[k][i]],muc[k][i]));
    }
    while(s.empty()==false)
    {
        auto it=s.begin();
        p=it->second;
        s.erase(it);
        for(i=0;i<muc[p].size();i++)
        {
            if(d[muc[p][i]]>d[p]+cost[p][i])
            {
                s.erase(s.find(make_pair(d[muc[p][i]],muc[p][i])));
                d[muc[p][i]]=d[p]+cost[p][i];
                s.insert(make_pair(d[muc[p][i]],muc[p][i]));
            }
        }
    }
    for(i=1;i<=n;i++)
    {
        if(d[i]!=INF)
        g<<d[i]<<" ";
        else
        g<<-1<<" ";
    }
    return 0;
}