#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)
        {
            while(!p.empty() && viz[p.begin()->second]==1)
                p.erase(p.begin());
            if(!p.empty())
            {
                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;
}