#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <climits>
#define Nmax 50001

using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int n, m;
int viz[Nmax];
int d[Nmax];
vector < pair<int, int> > gr[Nmax];
set < pair<int, int> > p;

int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        f>>x>>y>>z;
        gr[x].push_back(make_pair(y, z));
    }
    for(int i=1;i<=n;i++)
    {
        d[i]=INT_MAX;
    }
    d[1]=0;
    p.insert(make_pair(0, 1));
    for(int i=1;i<=n;i++)
    {
        if(p.size()!=0)
        {
            pair<int, int> fr=*p.begin();
            p.erase(p.begin());
            for(auto j:gr[fr.second])
            {
                if(viz[j.first]==0 && d[j.first]>d[fr.second]+j.second)
                {
                    d[j.first]=d[fr.second]+j.second;
                    p.insert(make_pair(d[j.first], j.first));
                }
            }
            viz[fr.second]=1;
        }
    }
    for(int i=2;i<=n;i++)
    {
        if(d[i]==INT_MAX)
            g<<"0 ";
        else
            g<<d[i]<<" ";
    }
    return 0;
}