#include <fstream>
#define DMAX 50010
#define INF 100000000
using namespace std;
ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");

struct tip {int nod, val;};

void citire();
void rez();
void afisare();
void init();

int n;
tip graf[DMAX][DMAX];

int dist[DMAX];
bool use[DMAX];

int valmin, indmin;

int main()
{
    citire();
    rez();
    afisare();
    
    fin.close();
    fout.close();
    return 0;
}

void citire()
{
    int i, m;
    int a, b, val;
    
    fin>> n>> m;
    for (i=1; i<=m; i++)
    {
        fin>>a>> b>> val;
        
        ++graf[a][0].val;
        graf[a][graf[a][0].val].nod = b;
        graf[a][graf[a][0].val].val = val;
    }
}

void rez()
{
    int k, i;
    
    init();
    
    for (k=1; k<=n-1; k++)
    {
        use[indmin]=1;
        for (i=1; i<=graf[indmin][0].val; i++)
        {
            if (!use[graf[indmin][i].nod])
            {
                if (dist[graf[indmin][i].nod] > dist[indmin] + graf[indmin][i].val)
                    dist[graf[indmin][i].nod] = dist[indmin] + graf[indmin][i].val;
            }
        }
        
        valmin = INF;
        for(i=1; i<=n; i++)
            if (!use[i] && dist[i]<valmin)
            {
                valmin = dist[i];
                indmin = i;
            }
    }
}

void init()
{
    int i;
    valmin = INF;
    
    for (i=2; i<=n; i++) dist[i]=INF;
    for (i=1; i<=graf[1][0].val; i++)
    {
        dist[graf[1][i].nod] = graf[1][i].val;
        if (graf[1][i].val < valmin)
        {
            indmin = graf[1][i].nod;
            valmin = graf[1][i].val;
        }
    }
    
    use[1]=1;
}

void afisare()
{
    int i;
    for (i=2; i<=n; i++) fout<< dist[i]<< ' ';
}