#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#define INF 0x3f3f3f3f

using namespace std;

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

vector <pair<int,int> > lista[50005];
vector<pair<int,int> >::iterator it;
queue <int> c
;

int dmin[50005],n,m;
bool viz[50005];

void citire()
{
    int a,b,c;
    f>>n>>m;
    for(int i=1;i<=m;i++)
        {f>>a>>b>>c;
         lista[a].push_back(make_pair(b,c));
        }
}

void prog()
{

int nod;
memset(dmin, 50005, sizeof(dmin));
memset(viz, false, sizeof(viz));
dmin[1]=0;
viz[1]=true;
c.push(1);
    while(!c.empty())
        {nod=c.front();
         viz[nod]=false;
         c.pop();
         for(it=lista[nod].begin(); it!=lista[nod].end(); ++it)
             if(dmin[nod]+it->second < dmin[it->first])
                {dmin[it->first]=dmin[nod]+it->second;
                    if(!viz[it->first])
                        {c.push(it->first);
                         viz[it->first]=true;
                        }
                }
        }
}
int main()
{
    citire();
    prog();
    for (int i = 2; i <= n; ++i)
        g << (dmin[i] < INF ? dmin[i] : 0) << " ";
}