#include <fstream>
#include <set>
#include <vector>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int N,M,A,B,C,drum[200005];
bool viz[200005];
const int INF=9999999;
vector <pair <int, int> > vecin[50005];
multiset<pair <int,int> > cale;
multiset<pair <int,int> >::iterator it;
int main()
{
    int sursa=1;
    fin>>N>>M;
    for(int i=1;i<=M;i++)
    {
        fin>>A>>B>>C;
        vecin[A].push_back(make_pair(C,B));
        if(i!=sursa) cale.insert(make_pair(INF,i));
        else cale.insert(make_pair(0,sursa));
        drum[i]=INF;
    }
    drum[sursa]=0;
    while(!cale.empty())
    {
        int nod=(*cale.begin()).second;
        cale.erase(cale.begin());
        while(!vecin[nod].empty())
        {
            int v=(*vecin[nod].begin()).second;
            if(!viz[v])
            {
                it=cale.find(make_pair(drum[v],v));
                if(it!=cale.end())
                    if(drum[(*it).second]>drum[nod]+(*vecin[nod].begin()).first)
                    {
                        cale.erase(it);
                        cale.insert(make_pair(drum[nod]+(*vecin[nod].begin()).first,v));
                        drum[v]=drum[nod]+(*vecin[nod].begin()).first;
                    }
            }
            vecin[nod].erase(vecin[nod].begin());
        }

    }
    for(int i=2;i<=N;i++)
    {
        if(drum[i]==INF) fout<<"0"<<' ';
        else fout<<drum[i]<<' ';
    }
    return 0;
}