#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");
priority_queue < pair < int,int > ,vector < pair <int,int> >,greater< pair <int,int>  >  > q;
int n,m,start,a,b,c,ma[5001][5001],d[50010],t[50010];
pair <int,int>cc;
bool viz[50010];
int main()
{
    fin>>n>>m;
    start=1;
    for(;m;m--)
    {
        fin>>a>>b>>c;
        ma[a][b]=c;
        ///ma[b][a]=c;
        if(a==start)
        {
            q.push({c,b});
            d[b]=c;
            t[b]=start;
        }
        /*
        if(b==start)
        {
            q.push({c,a});
            d[a]=c;
            t[a]=start;
        }*/

    }
    viz[start]=1;
    while(!q.empty())
    {
        cc=q.top();
        q.pop();
        ///fout<<cc.first<<" "<<cc.second<<endl;
        viz[cc.second]=1;
        if(d[cc.second]==cc.first)
        {
            for(int i=1;i<=n;i++)
            {
                if(ma[cc.second][i]!=0&&i!=start)
                {
                    if((ma[cc.second][i]+d[cc.second]<d[i]||d[i]==0)&&d[cc.second]!=0)
                    {
                        d[i]=d[cc.second]+ma[cc.second][i];
                        t[i]=cc.second;
                        q.push({d[i],i});
                    }
                }
            }
        }
    }
    for(int i=2;i<=n;i++)
    {
        if(d[i]==0&&i!=start)
            fout<<-1<<" ";
        else
            fout<<d[i]<<" ";
    }
    /*
    fout<<endl;
    for(int i=1;i<=n;i++)
    {
        fout<<t[i]<<" ";
    }
    */
    return 0;
}
/*
7 1
1 2 2
1 4 8
1 5 7
2 3 3
2 5 4
2 7 4
3 4 1
3 6 10
4 7 9
4 5 2
5 7 5
*/