#include <fstream>
#include <cstring>
#include <climits>
using namespace std;
#define max_n 50001
#define max_m 250001
#define inf 1061109567
int n,m,s,e[max_m][3],d[max_n];
int t[max_n];
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
void drum (int i)
{
    if (t[i])
        drum(t[i]);
    g<<i<<" ";
}
void bellman (int s)
{
    int i,nr,k,j,c,ok;
    memset (d,inf,sizeof(d));
    d[s]=0;

    for (ok=nr=1;ok && nr<n;nr++)
        for (ok=k=0;k<m;k++)
            {
                i=e[k][0];
                j=e[k][1];
                c=e[k][2];
                if (d[j]>d[i]+c)
                    {
                        d[j]=d[i]+c;
                        ok=1;
                        t[j]=i;
                    }
            }
}
int main()
{
    int i;
    f>>n>>m;
    for (i=0;i<m;i++)
        f>>e[i][0]>>e[i][1]>>e[i][2];
    bellman (1);
    for (i=2;i<=n;i++)
        if (d[i]!=inf)
        {

            g<<d[i]<<" ";
        }
        else
        g<<0<<" ";
    return 0;
}