#include <iostream>
#include <fstream>
#include <vector>
#include <climits>
#define Nmax 20001

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];

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;
    for(int i=1;i<=n;i++)
    {
        int dmin=INT_MAX, nr=-1;
        for(int j=1;j<=n;j++)
        {
            if(viz[j]==0 && dmin>d[j])
            {
                dmin=d[j];
                nr=j;
            }
        }
        if(nr!=-1)
        {
            for(auto j:gr[nr])
            {
                if(viz[j.first]==0)
                {
                    d[j.first]=min(d[j.first], d[nr]+j.second);
                }
            }
        }
        viz[nr]=1;
    }
    for(int i=2;i<=n;i++)
    {
        if(d[i]==INT_MAX)
            g<<"0 ";
        else
            g<<d[i]<<" ";
    }
    return 0;
}